linear algebra - Is there a simple algorithm for calculating the maximum inscribed circle into a convex polygon?

Question

I found some solutions, but they're too messy.

Answer 1

Yes. The Chebyshev center, x*, of a set C is the center of the largest ball that lies inside C. [Boyd, p. 416] When C is a convex set, then this problem is a convex optimization problem.

Better yet, when C is a polyhedron, then this problem becomes a linear program.

Suppose the m-sided polyhedron C is defined by a set of linear inequalities: ai^T x <= bi, for i in {1, 2, ..., m}. Then the problem becomes

maximize  R
such that ai^T x + R||a|| <= bi,  i in {1, 2, ..., m}
          R >= 0

where the variables of minimization are R and x, and ||a|| is the Euclidean norm of a.