algorithmlinear-algebralinear-programmingconvex-optimizationconvex-polygon

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

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

Solution

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