Timeline for Efficiently determine if convex hull contains the unit ball
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 11, 2013 at 11:22 | comment | added | Manfred Weis | A first step to prove that it could be polynomial, would be to prove that it is not necessary to check $O(n^{\lceil d/2 \rceil})$ faces of the convex hull; I doubt that that is possible. Suppose you have a convex hull that contains the unit ball; intersect that with a halfspace that contains the origin and intersects the unit ball hoping to be able to detect efficiently from the resulting set of points the ones that define the hyperplane that cuts the unit-ball is very optimistic. | |
| Sep 11, 2013 at 10:44 | comment | added | Simd | I suppose an interesting subquestion is whether it is even in NP. However I am not sure one can rule out a polynomial time algorithm so easily. | |
| Sep 11, 2013 at 10:08 | comment | added | Manfred Weis | @octonots as the construction of the convex hull is exponential in $d$, the answer to your question is no, because if the unit sphere is inside the convex hull, it can come arbitrarily close to a face, while the distance to the vertices may stay above some fixed value; so one has to construct the hyperplanes through the faces of the convex hull in order to calculate their distance from the origin. | |
| Sep 11, 2013 at 10:03 | history | edited | Manfred Weis | CC BY-SA 3.0 |
treated the case of the unit ball at the origin.
|
| Sep 11, 2013 at 9:56 | comment | added | Simd | Thank you. I consider $n^{\lceil d/2 \rceil}$ to be exponential in $d$ however. My question is whether there is an algorithm that is polynomial in both $n$ and $d$. | |
| Sep 11, 2013 at 8:04 | history | edited | Manfred Weis | CC BY-SA 3.0 |
described, how to proceed if only the points on the convex hull are to be taken into account.
|
| Sep 11, 2013 at 7:44 | history | edited | Manfred Weis | CC BY-SA 3.0 |
improved the answer
|
| Sep 11, 2013 at 6:36 | history | answered | Manfred Weis | CC BY-SA 3.0 |