Skip to main content
MathOverflow

Return to Question

added a characterization of $C$ pursuant to Alex's comment
Source Link
Tom Solberg
Tom Solberg
  • 1
  • 1

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).

Let $x_0$ be a point contained inside a compact, convex set $C\subset\mathbb{R}^d$. 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).

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).

Source Link
Tom Solberg
Tom Solberg
  • 1
  • 1

Largest ball with fixed center in a a convex region

Let $x_0$ be a point contained inside a compact, convex set $C\subset\mathbb{R}^d$. 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).