最小面积四边形算法

Question

有一些算法可以找到包含给定(凸)多边形的最小边界矩形.

有没有人知道找到最小区域边界四边形(任何四边形,而不仅仅是矩形)的算法？

我现在在互联网上搜了好几个小时了,但是虽然我发现了一些关于这个问题的理论论文,但我没有找到一个实现...

编辑:Mathoverflow的人向我指出了一篇带有数学解决方案的文章(我的帖子),但我没有找到实际的实现.我决定采用卡尔的蒙特卡罗方法,但是当我有时间的时候,我会潜入报纸并在这里报道......

谢谢大家!

Answer 1

蒙特卡洛方法

感谢您对该问题的澄清评论.我已经拿走了所需要的不是一个数学上正确的结果,而是一个"适合",它比任何类似的其他形状的适合性更好.

我没有在这个问题上投入大量的算法脑力,而是让计算机担心它.生成4个随机点组; 检查由凸起连接这4个点形成的四边形是否与多边形不相交,并计算四边形的面积.重复100万次,检索面积最小的四边形.

您可以应用一些约束来使您的点不是完全随机的; 这可以大大提高收敛性.

蒙特卡洛,改进了

我一直相信,即使对于蛮力解决方案,在飞机上随机投掷4点也是一个非常低效的开始.因此,以下改进:

• 对于每个试验,随机选择p个不同的顶点和q个不同的多边形边,使得p + q = 4.
• 对于每个q侧,构造一条穿过该侧的端点的线.
• 对于每个p个顶点,构造一条穿过该顶点并具有随机分配的斜率的线.
• 验证4条线确实形成四边形,并且该四边形包含(并且不相交!)多边形.如果这些测试失败,请不要再进行此迭代.
• 如果此四边形区域是迄今为止所见区域的最小值,请记住四边形顶点的面积和坐标.
• 重复任意次数,并返回找到的"最佳"四边形.

与总是需要8个随机数(4个点中的每一个的x和y坐标)相反,该解决方案仅需要(4 + p)个随机数.而且,产生的线不是在平面中盲目地挣扎,而是每个都接触多边形.这确保了四边形从一开始就至少非常靠近多边形.

Answer 2

吝啬的算法

从凸多边形开始。当点数超过 4 个时，找到合并成本最低的一对相邻点，然后合并它们，将多边形中的点数减少 1。

通过“合并”，我的意思是将两侧的两条边延伸直到它们在一点相交，然后以该点替换这两条边。

“最便宜”是指合并为多边形增加最小面积的对。

Before:                       After consolidating P and Q:

                                    P'
                                   /\
   P____Q                         /  \
   /    \                        /    \
  /      \                      /      \
 /        \                    /        \

在 O(n log n) 中运行。但这仅产生近似值，我对此并不完全满意。算法在生成漂亮的正五边形方面做得越好，最后一次合并必须吃掉的区域就越大。