是否有一种简单的算法可以将最大内切圆计算为凸多边形? [英] Is there a simple algorithm for calculating the maximum inscribed circle into a convex polygon?

问题描述

我找到了一些解决方案，但是它们太混乱了.

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

推荐答案

是.集合C的 Chebyshev中心 (x *)是中心位于C内最大的球. 416]当C是一个凸集时，那么这个问题就是一个凸优化问题.

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.

更好的是，当C是多面体时，那么这个问题就变成了线性程序.

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

假设m面多面体C由一组线性不等式定义:ai ^ T x< = bi，对于{1,2，...，m}中的i.然后问题就变成了

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

其中最小化变量是R和x，而||a||是a的欧几里得范数.

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

这篇关于是否有一种简单的算法可以将最大内切圆计算为凸多边形?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！