Timeline for Intersecting a convex polytope with the unit sphere

Current License: CC BY-SA 3.0

15 events

when toggle format	what		by	license	comment
Dec 10, 2016 at 16:52	vote	accept	CommunityBot
Dec 10, 2016 at 10:38	comment	added	Dima Pasechnik		it is indeed hard to do, see my answer below.
Dec 10, 2016 at 10:37	answer	added	Dima Pasechnik		timeline score: 5
Dec 10, 2016 at 9:40	comment	added	Dima Pasechnik		But this most probably can only be done in exponential time. The hard case seems to be able to check whether the polytope is contained in the interior of the unit ball $B$. Indeed, one can check quickly whether the intersection of the polytope and $B$ is nonempty, but this is not quite enough.
S Dec 10, 2016 at 8:47	history	suggested	Rodrigo de Azevedo		added tag to question
Dec 10, 2016 at 8:31	review	Suggested edits
S Dec 10, 2016 at 8:47
Dec 10, 2016 at 2:01	comment	added	Igor Rivin		@YoavKallus Unfortunately, this is exponential time, in general (since the number of vertices is potentially exponential in the number of constraints.
Dec 10, 2016 at 0:42	answer	added	Rodrigo de Azevedo		timeline score: 2
S Dec 9, 2016 at 18:30	history	suggested	Rodrigo de Azevedo	CC BY-SA 3.0	minor edits
Dec 9, 2016 at 18:20	review	Suggested edits
S Dec 9, 2016 at 18:30
S Dec 9, 2016 at 16:41	history	suggested	Henry.L		more relevant tags
Dec 9, 2016 at 16:30	review	Suggested edits
S Dec 9, 2016 at 16:41
Dec 9, 2016 at 16:24	comment	added	user47305		Ah, when you phrase it like that it is much simpler! Thanks. (I wouldn't object if someone wants to close this question.)
Dec 9, 2016 at 15:46	comment	added	Yoav Kallus		Do you want to show that the polytope is entirely outside the sphere or entirely inside it? For the first, you only have to exhibit a separating plane with the sphere on one side and the polytope on the other. For the second, you have to show that all the polytope vertices are inside the sphere.
Dec 9, 2016 at 15:27	history	asked	user47305	CC BY-SA 3.0