All Questions
Tagged with convex-polytopes computational-geometry
45 questions
0
votes
0
answers
37
views
Constructing a minimum-volume outer approximation polytope with fewer facets
I am tackling the following problem:
Given a set of points $D \in \mathbb{R}^d$ and their convex hull, represented with $n$ facets, I want to construct a convex polytope $P$ with at most $m<n$ ...
- 101
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 ...
- 723
1
vote
0
answers
110
views
Upper bound on the diameter of a convex lattice n-gon with a given area
Given the area $A$ of a strictly convex polygon with $n$ vertices with integer Cartesian coordinates, there are usually several non-equivalent polygons. The relationship between the area, the number ...
- 206
1
vote
0
answers
58
views
Are cells of 4-polytopes a convex polyhedron by definition?
I'm going by the Wikipedia definition for a 4-polytope.
Do by definition, cells of 4-polytopes have to be a convex polyhedra?
If not, then are there polyhedra with non-convex faces?
If yes, is it the ...
- 11
2
votes
1
answer
113
views
Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points
Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$.
Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that
$$
\theta ...
- 6,853
3
votes
0
answers
51
views
testing whether a polyhedral complex is convex
Definitions
A (polyhedral) cone in $\Bbb R^n$ is the solution set of a finite number of inequalities of the form $a_1x_1+\cdots+a_nx_n\geq 0$. Note that I don't require strict convexity, i.e. a cone $...
- 3,079
1
vote
1
answer
1k
views
Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]
Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
- 11
0
votes
0
answers
54
views
Attached convex "hulls"
Let $\mathcal{P}$ a finite set of points of a Euclidean $\mathbb{E}^n$ and take the union $\mathrm{U}(\mathcal{P})$ of all closed half-spaces defined by $n$ elements of $\mathcal{P}$ that contain only ...
- 13.2k
1
vote
0
answers
62
views
fast V representation update of polytope
Say that I have both the V and the H representation of a (possibly unbounded) polytope $P$. I want to append a some rows to the H representation, how can I quickly update the V representation to ...
- 155
1
vote
0
answers
43
views
Vertex enumeration for polytope with a sparse halfplane description?
Say I have a (bounded convex) polytope $P\subset\mathbb R^d$ with description $Ax\le b$, where $A$ is sparse in the sense that there are at most $k$ nonzero entries in each row or column, where $k$ is ...
- 523
1
vote
0
answers
52
views
How does one translate from convex hull to a set of facets (inequalities)? [duplicate]
Suppose I have defined a convex set as the convex hull of a set of points. (I know that all these points are "extremal points" of the convex set.) I know want to translate this description of the ...
- 11
1
vote
1
answer
99
views
Estimating volume of a simple object
Volume computation is $\#P$ hard.
Take the $[0,1]^n$ polytope.
Slice it by an half space inequality with $poly(n)$ bit rational coefficients into two unequal halves.
Volume of bigger section is $\...
- 13.9k
6
votes
0
answers
237
views
Complexity of scissors congruence?
Where is the complexity of the problem 'Given two bounded compact convex integral polyhedra in $\mathbb R^n$ presented by $O(poly(n))$ integer valued halfspaces given by linear inequalities with ...
- 13.9k
1
vote
0
answers
68
views
Projection of a polytope along 4 orthogonal axes
Consider the following problem:
Given an $\mathcal{H}$-polytope $P$ in $\mathbb{R}^d$ and $4$ orthogonal vectors $v_1, ..., v_4 \in \mathbb{R}^d$, compute the projection of $P$ to the subspace ...
- 11
3
votes
1
answer
291
views
How to find the vertices of the set $\{v_i\in \mathbb{R}:a_1\ge v_1\ge v_2\ge \cdots\ge v_n\ge 0,\ q_2\le \sum_{i=1}^n p_iv_i\le q_1\}$
I am given a set of inequalities $v_1\ge v_2\ge \cdots\ge v_n\ge 0$, $q_2\le \sum_{i=1}^n p_iv_i\le q_1$, with $\{p_i\}_{i=1}^n,\ q_1,q_2$ positive reals, and only one bound for the coordinates: $v_1\...
1
vote
0
answers
48
views
Efficient scissors congruence between efficiently describable convex polytopes and simplex?
Is there a convex polytope in $\mathbb R^n$ describable by only $O(poly(\log n))$ half-plane inequalities with positive volume (so at least $n+1$ vertices) such that the standard simplex has a ...
- 1,826
1
vote
0
answers
65
views
Covering a simplex efficiently by efficiently describable polytopes?
Take a standard simplex or cube in $\mathbb R^n$.
Is there a way to cover it with $O(poly(\log n))$ convex polytopes each describable by only $O(poly(\log n))$ half-plane inequalities?
If not what ...
- 1,826
1
vote
0
answers
64
views
Polytopes that can be efficiently described and efficiently covered by cubes or simplices?
Is there a bounded convex polytope $\mathcal P\subseteq\mathbb R^n$ with $m$ vertices, whose vertex vectors span $\mathbb R^n$ (so $m$ is $\Omega(n)$) and just $O(poly(\log n))$ half-plane ...
- 1,826
4
votes
2
answers
734
views
Fast projection onto a subspace
Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...
- 1,677
2
votes
1
answer
349
views
Several convex polytopes in a simplex; fix an extreme point for each; how many can be supported by a function monotonic on all line segments?
Sorry the title may be unclear. I do not know how to give it a good title.....
Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$....
- 159
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,194
0
votes
1
answer
79
views
algorithms and tools available for a particular polytope computation
Let me define each half space i as:
$${H_i}:{c_i}{\bf{x}} \le {b_i}$$
The intersection of all such ${H_i}$ gives a polyhedron (bounded or not). Suppose I am interested in if ${H_i}$ is active (...
- 867
2
votes
0
answers
49
views
Algorithm for Finding the Center of an Optimal Stereographic Projection
given a fnite set $\mathcal{P}$ of points on a $n$-sphere $\mathcal{S}$ and, define a function $f:(s,\mathcal{P})\mapsto\mathbb{R}_0^+$, that maps each point $s$ on $\mathcal{S}$ to the $n$-volume $...
- 13.2k
5
votes
2
answers
755
views
Intersecting a convex polytope with the unit sphere
I have a list of $m$ affine inequalities in $n$ variables of the following form
$$a_1 x_1 + \cdots + a_n x_n \leq c_n$$
I would like to know whether there is any point on the unit sphere in $\...
user47305
6
votes
1
answer
2k
views
Approximation of convex hull in high dimension
What are efficient methods (polytime) to compute an approximation of the convex hull in high dimension (say, $30000$) for a given set of points?
Edit:
I am looking for an algorithm for getting the ...
- 61
1
vote
0
answers
368
views
Convex hull of the intersection of nonconvex sets
I have a set $D$ in $\mathbb{R}^{d+1}$ which is the intersection of $d$ domains $D_i$ given by $f(x_{i}) \leq x_{i+1} \leq g(x_{i})$ for two functions $f$ and $g$.
I want to find the convex hull of $...
- 31
0
votes
0
answers
63
views
Distinguishing (possibly lower dimensional) $1$-skeleton of a regular graph inscribed in a sphere
Consider you have two (possibly same) convex $1$-skeleton of a regular graph $A$ and $B$ in $m$-dimensions inscribed in a sphere with possibly exponential number of vertices in $n$-dimension with ...
user76479
1
vote
1
answer
391
views
Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces
Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by
$$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$
$$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$
I wish to find their convex hull, that is a ...
- 2,689
0
votes
0
answers
52
views
Efficient sampling from a polytope with large number of contraints [duplicate]
As far as I know, the most popular way to sample from a polytope (in H-representation)
\begin{equation}
\mathcal{P} := \{z \in \mathbb{R}^n | (Az)_j \le b_j\; \forall j=1,2,\ldots,m\}
\end{equation}
...
- 6,853
-1
votes
2
answers
640
views
Maximal-Orthogonal Convex Hull (or Maximal-Rectilinear Convex Hull) [closed]
Edit : Consider giving a reason for down vote.
In my research, I have come across a this paper from the Computational Geometry field and I am not able to understand the concept of Maximal-...
- 119
2
votes
1
answer
248
views
Choosing the weights of a Voronoi diagram -- is this function always the gradient of another function?
This question is related to the earlier question Weighted area of a Voronoi cell . As in that question, let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,...
- 4,049
5
votes
2
answers
153
views
Expressing a convex Polytope as a sublevel set of a function
Given an n-dimensional polytope $P$ in $\mathbb R^n$, Given as a convex hull of a finite set of points, $S$ I would like to construct an expliict formula for a function $f\colon \mathbb R^n \to \...
- 1,893
10
votes
1
answer
3k
views
Computionally efficient vertex enumeration for (convex) polytopes
Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be ...
- 321
10
votes
1
answer
565
views
The intersection of two $l_1$ balls
Let $B_1$ and $B_2$ be two balls in $\mathbb{R}^n$ with respect to the $l_1$ norm that have different radii and different centers. Is there an upper bound for the number of vertices that $B_1\cap B_2$...
- 131
3
votes
0
answers
149
views
Dead Flies Problem [duplicate]
If a set of points in the plane contains one point in each convex region of
area 1, then can it have finite density?
what is the density of the points? In my understanding, it means the average ...
user39815
3
votes
1
answer
141
views
Number of lattice polytopes contained in a given lattice polytope?
Given a (convex) lattice polytope, suppose we want to list or count all (convex) lattice polytopes (of the same dimension) contained in it. Are there efficient ways to do this?
- 495
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
17
votes
2
answers
2k
views
Efficiently determine if convex hull contains the unit ball
Given a set of $n$ points in $\mathbb{R}^d$, is there an algorithm to determine if the convex hull contains the unit ball centered at the origin in polynomial time (in both $n$ and $d$)? The convex ...
- 3,377
4
votes
1
answer
367
views
convex polyhedron in the unit cube
Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where $\...
- 165
1
vote
2
answers
431
views
Higher dimensional convex hull
Let $CH(S)$ be a convex hull of a finite set $S$ and denote the set of all the vertices of $CH(S)$ as $Vert(S)$. For a vertex $v \in Vert(S)$, it has an associated set $E(v)$ which is defined as $E(v)=...
user33954
15
votes
2
answers
3k
views
Given the vertices of a convex polytope, how can we construct its half-space representation?
Let us say I have the vertices of a polytope $V = \{v_1,\dots,v_k\} \subset \mathbb R^n$. Is it possible to write $V$ as intersection of half-spaces using the information from the vertices, i.e., can ...
- 173
1
vote
0
answers
185
views
Compute generalized pentagram map
Hi,
(This is my first question on MathOverflow! :-)
Imagine you have a set of points $S = \{p_1, \ldots, p_n\}$ in $\mathbb{R}^d$, of which $t$ are "bad". I want to compute a "safe convex hull", ...
- 11
16
votes
2
answers
5k
views
Weighted area of a Voronoi cell
Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
- 195
11
votes
3
answers
6k
views
Random Sampling a linearly constrained region in n-dimensions...
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
- 113
4
votes
1
answer
3k
views
intersection of convex and non-convex polyhedra
I am trying to find the best appropriate way to intersect polyhedra which may be non-convex.
The number of vertices that build the polyhedron is hence always small (up to 20 or so).
The ...
- 143