使凸多边形形状平滑,使其在保持直径的同时变得尽可能大

Question

鉴于凸多边形,我试图在保持其直径的同时增长其形状(如"最大区域").直径定义为可放置在多边形内的最长段的长度.由于多边形是凸的,我假设通过扫描所有顶点对总能找到这个直径.

例如,给定等边三角形作为输入多边形,三角形的直径是任何边的长度; 平滑这将导致3个圆段,如图所示

对于任意凸多边形,一种非常低效的算法是计算以每个多边形顶点为中心的最大直径半径圆的交点; 这就是我目前使用的(Java).有更好的吗？任何伪代码或指向算法的指针都将受到赞赏.

另一个例子:压扁的五边形及其相应的直径保持最大形状.这个想法是你不能在不增加直径的情况下增加这种形状的面积(也就是说,可以在比原始直径更长的形状范围内画出一条直线).在这种特殊情况下,似乎半径= polygon_diameter/2(粉红色)的单个圆优于半径= polygon_diameter(浅蓝色)的多个较大圆的交点.第二个图像叠加两个区域以使比较更容易,但区域应完全包围多边形.

Answer 1

事实证明这个问题已经在Math Overflow上被问过上被问过，人们认为这可能是一个难题。甚至还有一些尚未解答的基本问题，例如这种形状是否独特。

\n\n

所以我没有确切的解决方案，但希望这能让您更接近或至少给您一些想法。

\n\n

背景

\n\n

为了简单起见，我们可以不失一般性地假设初始多边形的直径为 1。

\n\n

盘多边形 Blaschke-Lebesgue 定理的推广（M. Bezdek，2009）描述了许多有用的概念。相关的包括：

\n\n

\n
• 非正式地，圆盘多边形是形成“胖”多边形的凸集，其中边被曲率 1 的圆弧替换。
\n
• 我们可以添加到点集D中的点集，使得所得形状的直径至多为 1，称为D的双盘多边形D*。
\n
• 对偶D**的对偶称为D的主轴凸包：它是包含D 的最小盘多边形。
\n

\n\n

与使用多边形不同，使用盘多边形就足够了：我们总是可以用其主轴凸包替换原始多边形，而不改变结果。

\n\n

当D 的直径为 1 时，我们有D \xe2\x8a\x86 D*，并且当且仅当D 的宽度为 1 时， D = D*。解S将具有恒定的宽度 1（尽管这当然还不够） 。因此D \xe2\x8a\x86 S当且仅当D \xe2\x8a\x86 S \xe2\x8a\x86 D*：特别是，为了近似S，我们只需要找到足够大的盘多边形子集D的S。这是非常强大的，因为正如我们将看到的，说某个点属于或不属于S会转化为S 的上限和下限（以及它的面积）。

\n\n

理论问题

\n\n

理想情况下，要找到一种有效的算法，回答以下问题将很有用：

\n\n

\n
• 全局最优形状（即解决方案）是否一定是唯一的？
\n
• 局部最优形状一定是唯一的吗？
\n
• 多边形的等径外壳一定是直径为 1 的圆还是宽度为 1 的鲁洛多边形？
\n
• 如果是这样，鲁洛多边形的顶点是否从原始多边形的顶点开始，从有限多个单位半径圆的交点导出？
\n
• 作为原始多边形顶点数量的函数，鲁洛多边形的顶点数量是否存在限制？
\n

\n\n

关于圆盘多边形面积的问题可能很困难：在将圆盘分开 - 平面中的克尼瑟-波尔森猜想(K. Bezdek, R. Connelly, 2001) 中解决的问题是一个关于圆盘相交面积的简单问题在这个平面上，这个问题已经很长时间没有解决了。

\n\n

实用的（？）方法

\n\n

全局搜索：
\n从多边形的主轴凸包开始，懒惰地构造一个递增盘多边形的无限搜索树，其中每个节点划分满足D \xe2\x8a\x86 X \xe2\的所有恒定宽度X的集合x8a\x86 D*，取决于D* \\ D的某个点x是否属于X。左分支是D \xe2\x88\xaa { x }的主轴凸包。右分支是D* \xe2\x88\xa9 { y : x \xe2\x88\x89 [ y , z ] 对于D中的所有z }的双盘多边形。

\n\n

除非您选择的x非常糟糕（例如在D* \\ D的边界上），否则该树的每条无限路径都应该收敛到恒定宽度的曲线。

\n\n

这个想法是以某种广度优先的方式探索树。希望，如果以合理的方式选择x，您将能够丢弃D* 的面积小于迄今为止发现的D的最大面积的所有分支，因为此类分支无法包含解决方案。然后，当您深入树时，您将拥有一组圆盘多边形，它们会收敛到问题的一组解决方案，但希望不会增长得太快。

\n\n

x的一些启发式方法可能是：取一个尽可能靠近D* \\ D内部的点，取一个随机点，等等。合并一定量的深度优先搜索以获得更精确的解决方案区域下限也可能很有趣，这将允许更快地丢弃树的整个分支。

\n\n

本地搜索：
\n我们还可以仅使用恒定宽度的圆盘多边形（Reuleaux 多边形），并查看小偏差的影响。但搜索空间相当大，因此尚不清楚如何做到这一点。

\n