Timeline for Efficiently determine if convex hull contains the unit ball
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Nov 6 at 15:22 | history | suggested | Don Hatch | CC BY-SA 4.0 |
clarify that "polynomial" is intended to mean "polynomial in both n and d", as the OP had to clarify several times in comments
|
| Nov 6 at 15:11 | review | Suggested edits | |||
| S Nov 6 at 15:22 | |||||
| S Nov 12, 2017 at 21:40 | history | suggested | Rodrigo de Azevedo |
Added tag to question
|
|
| Nov 12, 2017 at 21:30 | review | Suggested edits | |||
| S Nov 12, 2017 at 21:40 | |||||
| Sep 12, 2013 at 10:36 | vote | accept | Simd | ||
| Sep 11, 2013 at 18:30 | answer | added | Yury | timeline score: 17 | |
| Sep 11, 2013 at 13:25 | history | edited | Simd | CC BY-SA 3.0 |
added 23 characters in body
|
| Sep 11, 2013 at 6:45 | comment | added | Simd | @ManfredWeis I mean the unit ball centered at the origin. In relation to your last question I am interested in worst case input configurations. Finally, the linear programming solution I referred to does indeed only use the points in the input without creating the potentially exponential number of half space queries en route. | |
| Sep 11, 2013 at 6:36 | answer | added | Manfred Weis | timeline score: 2 | |
| Sep 11, 2013 at 6:13 | comment | added | Manfred Weis | Yet another question: are the $n$ points in convex configuration or can some of the points be inside the convex hull? Is it assumed that the convex hull is $d$-dimensional? | |
| Sep 11, 2013 at 5:49 | comment | added | Manfred Weis | In your answer to Igor Rivin you mentioned linear programming for checking whether a point is inside the convex hull; in linear programming the points of the convex hull are not explicitly given, but rather implicitly via the intersection of half-spaces. Maybe you should rethink, how your convex hull is given, via points or via the intersection of half-spaces. In the latter case the problem can be solved efficiently via linear programming | |
| Sep 11, 2013 at 5:26 | comment | added | Manfred Weis | how is the set of points given? They could be either in random order or, be sorted in some way (e.g. lexicographical). Further, you should define what is meant by "the unit ball": is it centered at the origin or did you mean "a unit ball", which could be centered anywhere? | |
| Sep 10, 2013 at 16:45 | comment | added | Simd | @IgorRivin I should have said. Polynomial in both $n$ and $d$. You can, for example, determine if an arbitrary fixed point is in the convex hull in polynomial time by a reasonably straightforward application of linear programming. | |
| Sep 10, 2013 at 16:38 | comment | added | Igor Rivin | Polynomial time in what? Are you fixing $d$ and varying $n,$ or are you varying both? | |
| Sep 10, 2013 at 12:57 | history | edited | Simd |
edited tags
|
|
| Sep 10, 2013 at 12:47 | history | asked | Simd | CC BY-SA 3.0 |