我一直在研究一个计算几何问题，并遇到了以下问题(这是作为子例程需要的)，但未能找到任何好的参考或算法。
给定一个简单的(可能是凹的)多边形p，目标是计算完全包含在p(空圆)中但至少在两个地方(点或边)接触多边形的最小圆的中心和半径。如果这两个"地方"恰好是多边形的点，那么就没有约束了。如果碰到一个点和一条边也没有约束条件。但是如果我们碰到两条边，那么它们不应该是连续的(假设顺时针或逆时针顺序)。
我的目标是一个可实现的算法运行在n^3或更好的顺序。任何指示、参考或想法都会很有帮助。
谢谢!Amer
既然你只是在寻找指示或想法，我就长话短说。多边形的中轴线是一组在两个或多个位置接触边界的圆的中心(https://en.wikipedia.org/wiki/Topological_skeleton#Centers_of_bi-tangent_circles)。中轴也被称为骨架，由直线和抛物线组成的树状图组成。如果您检查此图顶点处的圆(忽略与多边形顶点重合的图形顶点)，您可以找到最大和最小的圆。你必须微调，以适应你的"无连续边"的要求。