All Questions
99 questions
7
votes
4
answers
706
views
A quick algorithm for calculating the $\ell_1$-distance between two finite sets on the real line?
For two non-empty finite sets $A,B$ in the real line define the $\ell_1$-distance $d_1(A,B)$ between $A$ and $B$ as the smallest Lebesgue measure of a closed subset $\Gamma\subset \mathbb R$ such that ...
- 41.8k
7
votes
2
answers
1k
views
Is a given point in the interior of the convex hull of a given finite collection of points?
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
- 96.4k
6
votes
2
answers
215
views
Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles
Definition: Let us refer to obtuse triangles with the largest angle strictly above a given cutoff value as 'strongly obtuse' - the definition is parametrized by the cutoff value. Likewise, strongly ...
- 5,979
6
votes
2
answers
189
views
Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon
For any point P in the interior of a convex polygon, the sum of the angles subtended by the edges of the polygon is obviously 2π.
Given a convex polygon, how does one algorithmically find the point (...
- 5,979
6
votes
1
answer
609
views
Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers
Let $a(n)$ be the Dirichlet inverse of the Euler totient function:
$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and let the matrix $T(n,k)$ be:
$$T(n,k)=a(\gcd(n,k)) \tag{2}$$
It has been ...
- 1,183
6
votes
0
answers
219
views
How big a box can you wrap with a given polygon?
Question: Given a convex polygonal region, how does one find the box (rectangular parallelopiped) of maximum volume that can be wrapped with this region? While wrapping, if needed, some portions of ...
- 5,979
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, ...
- 41.8k
6
votes
2
answers
8k
views
Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations
Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $...
6
votes
1
answer
761
views
Checking if one polytope is contained in another
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...
- 491
6
votes
0
answers
157
views
On cutting disks from planar regions
Question: Given a planar region $R$ of unit area and an integer $n$, to cut $n$ circular disks (their sizes need not be equal) such that the highest fraction of $R$ is taken off.
A simple greedy ...
- 5,979
6
votes
5
answers
4k
views
Formulas for equidistant curves
I'm trying to draw on the computer a curve that keeps always the same distance(given as parameter) from a given curve. I know the formula for the given curve. I tried moving perpendicular to the first ...
- 351
5
votes
0
answers
213
views
Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell
Given an $n \times n$ grid with unit grid cells, and one point from the interior
of each cell, what is are best possible lower and upper bounds for lengths of minimum spanning trees? The lower bound ...
user71114
5
votes
0
answers
309
views
Upper bounds on art gallery problems using independent witnesses
Given a polygon $P$, the art gallery problem looks to find a smallest set of points that sees all of $P$. One way of bounding the number of guards necessary (from below) is to find a largest set of ...
- 1,182
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?
...
- 3,059
5
votes
2
answers
294
views
Convex caps with prescribed edges
Let $P$ be a convex polygon in the plane $R^2=R^2\times \{0\}$, and $E$ be the edge graph of some subdivision of $P$ into convex polygons, which is $3$-connected. Does there exist a convex polyhedral ...
- 7,149
5
votes
1
answer
169
views
Connectedness of semialgebraic sets via CAD
I do not know whether there is a standard or some traditional ways to decide whether a semialgebraic set is connected or not.
One way I know is the cylindrical algebraic decomposition (CAD) algorithm. ...
- 61
4
votes
1
answer
204
views
Reference: Packing under translation is in NP
I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...
- 479
4
votes
1
answer
891
views
Basic result in semi-infinite linear programming
Consider a standard linear program of the form $$\textrm{minimize}_x~~~~ c^Tx~~~~ s.t. \\ Ax = b \\ x \geq 0$$ with $x\in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. It is well known that, if ...
- 4,049
4
votes
2
answers
424
views
Algorithm for Reconstructing Point Sites from a Voronoi Diagram
how can one construct a finite set of points in the euclidean plane from its Voronoi Diagram and, what is the complexity of the problem?
- 13.2k
4
votes
1
answer
1k
views
How to compute the tangent space of a quotient by a finite group
Let $I\subseteq R:=\mathbb C[x_0,\ldots,x_n]$ be a homogeneous ideal defining a subscheme $X\subseteq\Bbb P^n$. As in my previous question, the permutation group $\mathfrak S_{n+1}$ acts on $R$ by ...
- 4,902
4
votes
2
answers
2k
views
Simplified knapsack problem
There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
- 41
4
votes
2
answers
390
views
Construct polygon/polyhedron containing all points not externally visible w.r.t given polygon/polyhedron?
Is there an algorithm to construct a polyhedron containing all points in space for which there exists no ray to infinite not intersecting a given polyhedron?
In 2D, we could consider polygons. For ...
- 723
4
votes
2
answers
2k
views
Breaking a rectangle into smaller rectangles with small diagonals
Say I am given a rectangle with dimensions $a \times b$ and an integer $n$. I'd like to break this rectangle into $n$ smaller rectangles $R_i$, and I'd like to make the maximum diagonal of any of ...
- 4,049
4
votes
0
answers
123
views
Cylindrical Decomposition vs Morse decomposition
Suppose I have a polynomial Morse function $f: \mathbb{R}^n \to \mathbb{R}$. Consider the ideal $I(\nabla f)$ generated by the partial derivatives $\partial_i f$, and assume that the real zero-set of ...
- 505
3
votes
1
answer
402
views
Computing intersections of unit disks
Given $n \geq 2$ points in the plane, how can one efficiently (or even inefficiently!) compute the number of corner-points belonging to the boundary of the intersection of the unit disks centered on ...
- 19.7k
3
votes
1
answer
10k
views
split polygon into minimum amount of rectangles and triangles
Hi
is there an algorithm which cuts a polygon into a minimum amount of preferably rectangles and where not possible (e.g. edges) into triangles?
3
votes
2
answers
791
views
complexity of finding optimal matchings of given fixed size
It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...
- 13.2k
3
votes
1
answer
1k
views
Regularity of Delaunay triangulation of a hypercube
First using a three dimensional unit cube as an example for the term "regularity", we can have two possible triangulations:
(A)
(B)
We say the lower triangulation is more "regular" than upper ...
- 339
3
votes
4
answers
4k
views
Existence of nonnegative solutions to an underdetermined system of linear equations
Similar questions have been asked elsewhere, but I think this is sufficiently different to warrant a new post. I have a particular matrix $A$ and would like to know when the system $Ax = 0$ has at ...
- 491
2
votes
2
answers
402
views
Is this a linear optimization problem? $Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative
$Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative.
What should $A$ satisfy to guarantee the equation set have only zero solution?
- 23
2
votes
1
answer
137
views
Design constraint systems over the reals
This question is inspired by the discussion at this problem.
Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...
- 30.1k
2
votes
1
answer
2k
views
Finding a point farthest away from $k$ points in a polygon
There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized.
...
- 57
2
votes
1
answer
173
views
Calculating the "Belvedere Hull" of a Simple Planar Polygon
As an informal motivation the problem, imagine a tower with polygonal footprint, that is located in a beautiful landscape, the "Belvedere Hull" is then related to the directions, in which one would ...
- 13.2k
2
votes
1
answer
84
views
'Constrained morphing' of planar convex regions
Morphing may be defined as a continuous transition of one shape to another. This post is about modifying planar regions continuously from one form to another under some constraints.
Qn: If $C_1$ and $...
- 5,979
2
votes
1
answer
116
views
Convex polyhedra that can be folded from convex polygons
This question is based on http://www.science.smith.edu/~jorourke/Papers/FoldingPP.pdf.
Therein is stated the theorem: Every convex polygon folds to an infinite number (a continuum) of noncongruent ...
- 5,979
2
votes
1
answer
197
views
Existence of solutions of polynomials systems (and their "rough" shape) over $\mathbb{R}$ & friends with positive-dimensional ideals
This is a follow-up (but self-contained) question to my previous one. There I asked about state-of-the-art methods to solve multivariate polynomials systems over non-algebraically closed fields in ...
- 697
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
1
vote
0
answers
92
views
Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent?
We add a bit to Tiling the plane with pair-wise non-congruent and mutually similar triangles and Cutting polygons into mutually similar and non-congruent pieces
A (non square) rectangle can obviously ...
- 5,979
1
vote
0
answers
72
views
A ratio to measure 'roundedness' of planar convex regions
Ref: A center of convex planar regions based on chords
The above discussion quotes the definition of 'centralness coefficient' and defines a center of a planar convex region. 1/2 is the least possible ...
- 5,979
1
vote
1
answer
144
views
On convex polygons contained in convex polygons
In what follows '$n$-gon' stands for '$n$-vertex polygonal region'.
Question: Given a convex $n$-gon $C$, find the smallest convex region $R$ such that $C$ is the smallest $n$-gon that contains it.
...
- 5,979
1
vote
1
answer
178
views
Inside-out dissections of solids -2
We record some general questions based on
Inside-out dissections of solids
Inside-out dissections of a cube
Can every convex polyhedral solid be inside-out dissected to a congruent polyhedral solid?...
- 5,979
1
vote
0
answers
111
views
On finding optimal convex planar shapes to cover a given convex planar shape
Covering a specific convex shape S with n copies of another specified convex shape S' (which may be different from S) is well studied - for example, https://erich-friedman.github.io/packing/index.html....
- 5,979
1
vote
1
answer
104
views
Finding the point within a convex n-gon that minimizes the largest angle subtended there by an edge of the n-gon
This post records a variant to the question asked in this post: Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon
Given a convex n-gon, ...
- 5,979
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
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
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$.
...
- 175
0
votes
0
answers
42
views
Construct pairs of $n$-dimensional convex bodies with given ratios ($p$) of volumes
Given a dimension $n$ and a number $p \in (0,1)$, to what extent is it possible (in what cases) to construct a convex set $A$--not a hypersphere--and a "snugly" inscribed (InscribedFigure) ...
- 723
0
votes
0
answers
63
views
Bounds for the Dispersal Problem in convex regions
We add a bit to: Bounds for minimax facility location in a convex region
Two earlier posts: Cutting convex regions into equal diameter and equal least width pieces - 2 and Facility location on ...
- 5,979
0
votes
0
answers
93
views
On smallest convex m-gons that contain a given n-gon where m<n
Given a convex n-gon region P, and an m less than n, will the least area convex m-gon Q that contains P be such that an edge of Q coincides with an edge of P (in other words Q cannot be such that P ...
- 5,979