All Questions
4 questions
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 ...
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 ...
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 ...
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 ...