将四边形拆分为最大面积的子区域

Question

将矩形/正方形拆分为更小的区域并增强每个子区域的最大面积非常简单。您可以将区域划分为边长为sqrt（max_area）的区域，并小心处理剩余物。

但是我很难过。假设我不知道任何角落的角度。我们还假设所有四个点都在同一个平面上。另外，我不需要这些小地区都是一样的大小。我唯一的要求是每个区域的面积都小于最大面积。

是否有一个特定的数据结构，我可以用它来使这更容易？
有没有一种算法，我只是没有找到？

我可以使用quadtrees来做到这一点吗？我不是非常精通树木，但我知道如何实现这个结构。

我在做这件事的时候记住了GIS的工作，但我相当确信这对分割四元组的算法没有影响。

Answer 1

您可以递归地将四边形在长边上分割成两半，直到产生的区域足够小。

Answer 2

如果你的四边形是凸面的，那么实际上你可以把它分成两个相同的区域，同时它们有相等的周长！这被称为公平划分，并在The Open Problems Project（它是开放的更大数量的片断，但解决了两件）描述。

对于非凸四边形，不难找到一条线将其划分为两个相等的部分，即 。
我相信这会起作用：通过一个 反射顶点，并旋转它的顶点，直到它平均分割区域。 同样的方法适用于凸多边形，如果您唯一的目标是将该区域划分为两个相等的半部分即 。

一般问题（对于任意多边形）取名为 “多边形的火腿三明治切片”。事实上，我写了一篇具有完全标题的论文。