All Questions
984 questions
6
votes
1
answer
374
views
Desargues ten point configuration $D_{10}$ in LaTeX
I want to draw the Desargues configuration $10_3$ in LaTeX using the standard picture environment, which allows only lines with the slopes $n:m$ where $\max\{|n|,|m|\}\le 6$. Is it possible? If not, ...
- 5,409
2
votes
0
answers
112
views
Understanding normalization algorithms
Let $R$ be a commutative and reduced ring, finitely presented over $\mathbb Z$. Let $\overline R$ be the integral closure of $R$ in its total ring of fractions. In https://arxiv.org/abs/alg-geom/...
- 211
1
vote
1
answer
119
views
Optimization on non-convex set
Let $\Omega$ be an open bounded subset of $\mathbb{R}^2$ and $f\in L^2(\Omega)$ be a given function. Consider the optimization problem
$$\mathrm{min} \int_\Omega u(x) f(x) \,dx\,,$$
where a minimum is ...
- 128k
2
votes
1
answer
132
views
Planar convex region maximizing the difference in 'orientation' between its smallest containing rectangle and largest contained rectangle
We say a rectangle has orientation $\theta$ if the vector from its center to the middle of its shortest side (parallel to the longest side) has some angle $\theta$ with X axis.
Consider a planar ...
- 115
1
vote
1
answer
78
views
To optimally wrap convex laminae with paper
Ref: On folding a polygonal sheet, Multi-layered wrapping of polyhedra
Basic intent: to wrap a given convex planar lamina with a convex sheet of non-stretchable paper (such that every point on both ...
- 151k
4
votes
3
answers
1k
views
Minimax theorem on a non convex domain
A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$:
$$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in \mathcal{...
1
vote
2
answers
124
views
Are there variants of Euclidean Steiner Tree problem that are known to be in P?
Question: The Euclidean Steiner Tree problem (https://en.wikipedia.org/wiki/Steiner_tree_problem) is NP hard. Are there non-trivial (constrained) variants of this question that are known to have ...
- 151k
1
vote
0
answers
78
views
Triangulation of polygons with all triangles having a common angle
Following Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles, we record another triangulation question.
Question: Given an n-vertex polygonal region ("n-...
- 5,979
0
votes
1
answer
51
views
What is the most dense sample for which the Crust algorithm returns an incorrect polygonal reconstruction?
The Crust algorithm by Amenta, Bern, and Eppstein computes a polygonal reconstruction of a smooth curve $C$ without boundary from a discrete set of sample points $S$. It is known that if $S$ is an a $\...
- 413
1
vote
0
answers
34
views
On partitioning convex polygonal regions in area ratio $t : (1-t)$ where $0<t<1/2$ with least length of cut
Question: Given a convex n-gon P. How can we efficiently find the partition of P into 2 pieces with areas in the some given ratio $t : (1-t)$ where $0<t<1/2$ such that the length of cut is ...
- 5,979
1
vote
1
answer
73
views
Partitioning polygons into obtuse isosceles triangles
Ref:
Partitioning polygons into acute isosceles triangles
Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles
https://math.stackexchange.com/questions/1052063/...
- 39.9k
2
votes
1
answer
504
views
Partitioning polygons into acute isosceles triangles
Question: Given an $N$-vertex polygon (not necessarily convex). It is to be cut into the least number of acute isosceles triangles.
Based on this MathSE discussion, one can think of a method to get $\...
- 5,979
5
votes
4
answers
540
views
How hard is it to determine if a weighted graph can be isometrically embedded in R^3?
Consider a graph $G$ with nonnegative edge weights.
Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight?
...
1
vote
0
answers
58
views
Covering a unit square with odd number of equal area triangles - optimally
We add a bit to this post: Cutting off odd numbers of equal area triangles from a unit square
Question: Given an odd integer n, how does one cover the unit square completely with n equal area ...
- 5,979
3
votes
2
answers
240
views
Writing a smooth plane quartic as the vanishing of $Q_0Q_2 - Q_1^2$ for quadratic $Q_0,Q_1,Q_2$
It seems well-known that any smooth plane quartic can be written as the vanishing of $Q_0Q_2 -Q_1^2$. Is there a good way to work out these quadratic factors $Q_0,Q_1,Q_2$? For example, given the ...
- 22.5k
3
votes
0
answers
95
views
Fast numerical integration of $\int_{[0,\:1)^d}\left|f_x(y)-g(y)\right|^p\:{\rm d}y$ for varying $x\in[0,1)^d$
Let $k\in\mathbb N$ and $y_1,\ldots,y_k\in[0,1)^d$ with $$\frac1k\sum_{i=1}^kh(y_i)\approx\int_{[0,\:1)^d}h(y)\:{\rm d}y\tag1$$ for every nice enough function $h:[0,1)^d\to\mathbb R$.
Now let $p\ge1$, ...
- 167
1
vote
0
answers
83
views
Counting Voronoi cells generated by lattice points
I am working on a problem in dynamical systems where I need to count Voronoi cells arising from nearest neighbours to a subset of the lattice. (See the picture below for an example: the shaded region ...
- 23.2k
3
votes
0
answers
144
views
Hemisphere containing the maximum number of points scattered on a sphere
Consider a set of points $x_1, \ldots,x_n$ on $\mathbb{S}^{k-1}$ (the unit sphere in $\mathbb{R}^k$). The goal is finding the hemisphere which contains the maximum number of $x_i$'s. Basically, we ...
- 9,501
1
vote
1
answer
3k
views
Covering an arbitrary polygon with minimum number of squares
I have a problem whereby, given an arbitrary polygon with any number of points, I need to cover the whole area by a number of fixed size squares. I can easily find a set of squares which covers the ...
- 1,446
3
votes
1
answer
271
views
Resultants and elimination theory
Consider an ideal $I = \langle f_1,\dotsc,f_n\rangle$ in the ring $k[x_1,\dotsc,x_m]$.
Define the $i$-th elimination ideal to be $I_i = I \cap k[x_{i+1},\dotsc,x_m]$.
For any two polynomials $f$ and $...
- 12.9k
2
votes
2
answers
2k
views
Finding points inside innermost convex hull [closed]
Given a set of points $S$ on the Euclidean plane, Onion Peeling determines the nested set $H$ of convex hulls on $S$. Define an analytical formula on $S$ which produces a point, not necessarily in $S$,...
- 1,446
13
votes
3
answers
1k
views
(non-)existence of the aperiodic monotile
The aperiodic monotile problem asks whether there exists a single tile that every tiling of the plane made with it results non-periodic. What is known about this problem? If this tile exists, how can ...
- 13.4k
2
votes
0
answers
126
views
Checking existence of a non-crossing Hamiltonian path in geometric graphs
I am interested in the following computational problem. Given a geometric graph (i.e, a graph drawn in the plane so that its vertices are represented by points in general position and its edges are ...
- 4,219
2
votes
0
answers
60
views
Biconvex Lens - an 'oriented' convex container for planar point sets
We continue On some optimal containers of a set of points on the 2D plane.
Let us define a biconvex lens as the intersection of two circular disks - not necessarily of the same radii. Such a figure ...
- 5,979
1
vote
2
answers
121
views
How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?
I am looking for an algorithm to solve the following optimization problem
$$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$
where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$.
...
0
votes
1
answer
119
views
How many samples do you need to get constant dispersion?
Let $C_n$ be the hypercube $[-1,1]^n$. For $a_1,\cdots,a_s \in C_n$, define its dispersion $D(a_1,\cdots,a_s)$ as $\max_{x \in C_n}\min_{i \in [s]} \|x-a_i\|_{2}$. Let $0< \lambda < 1$ be a ...
- 261
17
votes
1
answer
580
views
Aperiodic monotile in $\mathbb{R}$
Motivation. Recently a group of researchers found an aperiodic monotile in $\mathbb{R}^2$, answering a long-standing question. There are many results in higher dimensions, so let's explore the lower ...
- 61.9k
6
votes
1
answer
631
views
On covering convex 2D regions with rectangles
Given a convex 2D region $C$ and a positive integer $N$. We need to cover $C$ with $N$ rectangles such that the sum of the areas of the $N$ rectangles is the least – no further constraints on the ...
CommunityBot
- 1
5
votes
3
answers
542
views
If a polyhedron in $\mathbb{R}^3$ has local intersections, does it also have more global intersections?
Consider a simplicial complex $K$. A piecewise linear map $f: K \to \mathbb{R}^n$ is an almost-embedding if $f(\sigma) \cap f(\tau) = \emptyset$ for any two disjoint simplices $\sigma,\tau$ in $K$.
...
- 976
1
vote
0
answers
82
views
Inside-out dissections of polygons - a generalization
Definitions (Inside-out polygonal dissections): a polygon P has an inside out dissection into P' if P′ is congruent to P and the perimeter of P becomes interior to P' and so the perimeter of P' is ...
- 5,979
2
votes
3
answers
2k
views
Better tactics for removing redundant constraints than Linear Programming?
After reading:
Detection of Redundant Constraints
It appears that linear-programming is the most commonly known way to remove ALL redundant constraints from a system of inequalities of the form
$$ ...
- 141
2
votes
1
answer
201
views
Dispersion of a "random" subset of $[-1,1]^2$
Let $C$ be the square $[-1,1]^2$. Let $a_1,\dots,a_m$ be points chosen independently and uniformly at random from $C$. Let $d_m$ (dispersion) be the random variable $\max_{x \in C}{\min_{j \in [m]}{\|...
- 1,170
2
votes
1
answer
85
views
Example of worst case distributions for 4D convex hull
My understanding is that convex hull of n points in 4D could have O(n²) edges in the worst case. Source: https://sites.cs.ucsb.edu/~suri/cs235/ConvexHull.pdf
This same source writes
In 4D, there are ...
- 151k
1
vote
1
answer
127
views
Smallest trapeziums containing a given convex n-gon
Question: Given a planar convex $n$-gon $C$, to find the smallest area / smallest perimeter trapezium (trapezoid) - a convex quadrilateral with at least one pair of mutually parallel edges - that ...
- 151k
0
votes
1
answer
103
views
Constrained linear optimization problem on $C^1$
I am dealing with a problem of the form ($a<b$)
$$
\displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...
3
votes
0
answers
65
views
Cutting triangles into triangles with equal longest side
This post elaborates on a specific instance of Cutting convex polygons into triangles of same diameter .
Question: For any integer n, can any triangle be cut into n non-degenerate triangles all of ...
- 5,979
1
vote
0
answers
36
views
Does Hoffman constant keep the same after a very tiny perturbation on the polyhedron such that the bases are even unchanegd?
Suppose that $P$ is a polyhedron represented by
$$P:=\{x \in \mathbb{R}^n: A x \le b \} \text{ for }A \in \mathbb{R}^{m\times n},\ b \in \mathbb{R}^m,$$
and $P$ contains interior points. Moreover, the ...
- 33
2
votes
0
answers
197
views
Is orthogonal polygon with crossings count NP-complete?
The are several NP-complete problems related to the construction of orthogonal simple polygons. Rapport showed that it is NP-complete to decide the existence of orthogonal simple polygon that passes ...
0
votes
0
answers
145
views
Bound on solutions of $Ax \ge b$
Let $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m \times 1}$.
One can show that if there is a solution of $Ax \ge b, x \in \mathbb{R}^n$ then there is one such that $\|x\|_{\infty} \le c (\|A\|_{...
- 439
1
vote
1
answer
119
views
Adding linear constraint to the domain
I don't know if it is a well-known problem, but I have been struggling to come up with an algorithm.
I have a set of linear constraints $Ax\le b$, $b\ge 0$ ($b$ and $A$ are given, $x$ is a variable). ...
- 5,429
0
votes
0
answers
84
views
1-degree SOS proof refutes Linear Programming
I am trying to understand Sums-of-Squares proof systems.
A degree $d$ Sums-of-Squares refutation for a set of polynomial equations $P = \{p_1(x) = 0, ..., p_m(x) = 0\}$ is defined as
$\sum_{i=1}^m g_i(...
3
votes
1
answer
107
views
Results in computational geometry utilizing doubling dimension of a metric space
According to Wikipedia,
However, many results from classical harmonic analysis and computational geometry extend to the setting of metric spaces with doubling measures.
My question is: what are some ...
CommunityBot
- 1
2
votes
1
answer
154
views
Do there exist smaller simplicial models of barycentric subdivisions?
Let $S$ be a simplicial complex and let $Bary(S)$ denote its barycentric subdivision.
Of course, the geometric realizations of $S$ and $Bary(S)$ are homeomorphic.
However, one issue that arises in ...
- 4,786
1
vote
0
answers
96
views
On optimizing a multivariate quadratic function subject to certain conditions
The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
- 61
14
votes
2
answers
540
views
Are all well behaved "mean" functions on $\mathbb{R}^+$ equivalent?
Given a set $S$, a function $M: S\times S \rightarrow S$ is a mean if it satisfies the properties:
$M(a,a)=a\qquad$ (identity)
$M(a,b)=M(b,a)\qquad$ (commutativity).
and possibly
$M(M(a,b),M(a,c))=...
- 27.7k
-2
votes
1
answer
248
views
Are there any non-elementary functions that are computable?
Does a function $\mathit{f}:\mathbb{R}→\mathbb{R}$ being non-elementary (not expressible as a combination of finitely many elementary operations), imply that it is not computable?
The particular case ...
- 236k
1
vote
0
answers
335
views
Closed-form solution of a particular linear program
(Note: I asked a similar question at math.stackexchange but the present one is more precise.)
I have a linear program of the form:
$$\text{minimize} \space\space x_1 \space\space \text{subject to:}$$
$...
- 4,219
5
votes
1
answer
255
views
Counting points above lines
Consider a set $P$ of $N$ points in the unit square and a set $L$ of $N$ non-vertical lines. Can we count the number of pairs $$\{(p,\ell)\in P\times L: p\; \text{lies above}\; \ell\}$$ in time $\...
- 121
5
votes
0
answers
167
views
Computing sums with linear conditions quickly
Let $f:\{1,\dotsc,N\}\to \mathbb{C}$, $\beta:\{1,\dotsc,N\}\to [0,1]$ be given by tables (or, what is basically the same, assume their values can be computed in constant time). For $0\leq \gamma_0\leq ...
- 20.2k
3
votes
1
answer
111
views
Constrained morphing of polygons
This post continues 'Constrained morphing' of planar convex regions
If an $m$-gon $P_m$ is to be morphed (altered continuously) into an $n$-gon $P_n$ with same area and perimeter, can one ...
- 151k