Let $x_0$ be a point contained inside a compact, convex set $C\subset\mathbb{R}^d$, which is of the form $C=\{x:f(x)\leq0\}$ for some explicit convex function $f$. Is there a computationally tractable way to find the largest ball, centered at $x_0$, that is contained inside $C$? When $C$ is a polyhedron defined by linear inequalities, this problem is trivial (just check the minimum distance to the boundary of each of the half-spaces defined by the inequalities).
5
-
3$\begingroup$ I think the computer tractability question would mainly depend on how $C$ is given. Do you have any "computer readable" representation in mind? $\endgroup$– Alex DegtyarevCommented Apr 1, 2015 at 17:35
-
$\begingroup$ Let's say it's the sub-level set of a convex function, $\{x:f(x)\leq 0\}$? Just edited the problem. $\endgroup$– Tom SolbergCommented Apr 1, 2015 at 17:40
-
1$\begingroup$ Try a coordinate system change: move $x_0$ to the origin and then use spherical coordinates. See if you can use some analysis to find an optimal r. Gerhard "Maybe Cylindrical Coordinates Will Work" Paseman, 2015.04.01 $\endgroup$– Gerhard PasemanCommented Apr 1, 2015 at 19:13
-
1$\begingroup$ I think Alex's point is that your question cannot be answered without a description of how $C$ is given. As a semi-algebraic set? $\endgroup$– Joseph O'RourkeCommented Apr 1, 2015 at 20:35
-
$\begingroup$ This is a borderline useless comment, but if you're willing to consider a "ball" in the $\ell_1$ sense, then all you'd have to do is check each of its $2d$ vertices, which would enable you to just do a simple bisection search on the "radius" and treat $f$ as a black box. $\endgroup$– John Gunnar CarlssonCommented Apr 2, 2015 at 6:27
Add a comment
|