是否有一个简单的算法来计算最大内接圆成凸多边形？ [英] Is there an simple algorithm for calculating maximum inscribed circle into a convex polygon?

问题描述

我找到了一些解决方案，但他们太乱了。

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

推荐答案

是的。该 切比雪夫中心 ，X *，一组C是中心那里面的谎言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.

假设米双面多面体C由一组线性不等式定义：AI ^ T X - 其中=双，其中i在{1，2，...，米}。那么问题就变得

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

，其中最小的变量研究和 X 和 || A | | 是欧几里得范数 A

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

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