给定点组成的的最小面积三角形

cyq32ent · 2024-08-04 15:05:50 · 算法·理论

### 一、$\mathcal O(n^3)$ 算法枚举所有点对即可。 ### 二、$\mathcal O(n^2)$ 算法 #### 1. 前置知识 ##### Line Arrangement(LA) 平面内的直线集 $L$ 中的 $N$ 条直线将平面分为 $\mathcal O(N^2)$ 部分，称作 $L$`导出的排列(Line Arrangement)`，用 $\mathcal A(L)$ 表示之。容易得知，平面的一些子区域是无穷大的 —— 所以，我们可以假定一个无穷远点 $P_{∞}$，认为所有直线交于 $P_{∞}$。另一种容易想到的做法是设置一个边界框。那么如何存储 $\mathcal A(L)$ 呢？—— ##### DCEL 这些直线构成了一个多边形网格，存储它的一种数据结构为 `双向链接边表(Doubly-Connected Edge List,DCEL)`。用它，可以找到一个点、边或面的邻域，而不需要枚举所有的面。先介绍几个概念：面、边、点，其中边和点与图论中的边与点类似；而若干个边和点围成的多边形称作面。现在考虑这张平面图（把平面多边形网格当成平面图）上的一条边。显然，它应该和两个面相邻。如果我们要逆时针遍历任意一个面的边，那么这条边应当是双向的。所以，我们将这条边拆成两条半边，它们长度、位置仍在原边上，但是带有方向。那么，每条半边只隶属于一个面。我们把同一条边拆成的两条半边称作孪生半边。下面，我们了解一下 DCEL 的结构。在 DCEL 的边中存储以下数据： - `Twin[e]`，即 `e` 的孪生边。 - `Origin[e]`，`e` 的起点。 - `Next[e],Prev[e]`，`e` 的前 / 后一条边。 - `IncidentFace[e]`，`e` 所属的面。 - 一些附加数据。在 DCEL 的点中存储以下数据： - `Coordinates[v]`，`v` 的坐标。 - `IncidentEdge[v]`，以 `v` 为起点的任意一条半边。 - 一些附加数据。在 DCEL 的面中存储一下数据： - `OuterComponent[f]`，`f` 边界上的任意一条半边。 - `InnerComponent[f]`，`f` 内部的空洞。这里不考虑。 - 一些附加数据。 ##### 构造 $\mathcal A(L)

假定 $|L|=n$，则 $|v|,|e|,|f|=\mathcal O(n^2)$，其中 $v,e,f$ 分别为 $\mathcal A(L)$ 上点、边、面的数量。构造直线排列的算法如下： - 构造边界框 $\mathcal B(L)

初始化 \mathcal A(L) \leftarrow \mathcal B(L)
枚举直线 L_i：
- 枚举直线 L_{1..i-1}：
- 获取 L_i\cap L_j = p。
- 确定 p 是否与一个包括边界的面相邻。这一步可以通过在 DCEL 的面上附加“是否为边界面” 的标记做到。
- 得到 L_i 穿过的边界面 f。

那么这个算法的复杂度是多少呢？其实我们想要知道的是以下部分的复杂度：

- 将 $f$ 被 $L_i$ 一分为二。 - $下一个被L_i穿过的面\leftarrow f$。

显然可以枚举 f 中所有的边做到它。我们引入一个概念：带域，即直线 L_i 穿过的所有面。带域的复杂度即这些面的复杂度之和。由此有带域定理：m 条直线组成的排列中，任意直线带域的复杂度为 O(m)。具体证明过程不再赘述。

做法

我们先将这些点所在的平面称作平面 S，现在构造一个平面 Q，使平面 S 内的点映射至平面 Q 的直线，而平面 Q 内的点映射至平面 S 的直线。我们称 Q 为 S 的对偶。

对于平面 S 内的任意两点 p_1,p_2，可确定一根直线 y=ax+b。那么，平面 S 内的直线 p_1p_2 可以映射至平面 Q 内的点 (a,b)。同样，考虑平面 Q 内的直线 b=\beta a+\gamma，它上面的所有点 (a,\beta a+\gamma)，都对应平面 S 内的一条直线 y=ax+(\beta a+\gamma)，而可以证明，对于所有的 a，y=ax+(\beta a+\gamma) 都经过某一点 (x_0,y_0)。这样，平面 Q 内的直线 b=\beta a+\gamma 映射到了平面 P 的点 (x_0,y_0)。

如上，我们 \mathcal O(n^2) 构造了平面 P 与平面 Q 的对偶。

对平面 Q 上的 n 条直线求直线的排列 \mathcal A(Q)。

枚举 P 上的点对 p_1,p_2，直线 p_1p_2 对偶到平面 Q 上的点 V。找到与 V 竖直距离最小的直线 L。确定 L 在平面 P 中的映射 p_3。容易证明，p_1p_2p_3 是以 p_1p_2 为底的最小面积三角形。（因为 p_3 必有与直线 p_1p_2 最短的距离）

那么如何找到与 V 竖直距离最小的直线呢？可以通过以下算法实现：

枚举 \mathcal A(Q) 上的面 F_i，对于每个面 F_i：
- 枚举 F_i 的顶点 V。V 即平面 S 内某条直线 l 的对偶。对于每个 V：
- 枚举 F_i 的边 E（注意，E 不与 V 相邻，因为与 V 相邻的 E 事实上就是 l 上的两个点）。更新 V 到 E 的距离。
- 计算最小三角形面积。

可以证明，该算法复杂度为 \mathcal O(n^2)。

LA 和 DCEL 在其他计算几何问题中也有广泛的应用。

参考资料

https://www.cs.umd.edu/class/spring2020/cmsc754/Lects/lect14-arrang-zone.pdf（直线排列）
https://stackoverflow.com/questions/3940604/minimum-area-triangle-from-a-given-set-of-points（关于最小三角形问题的讨论）
https://barequet.cs.technion.ac.il/teaching/cg/fa20/CG-lecture9-LA.pdf (提了一下直线排列的应用)
http://www.opita.net/node/402（\mathcal O(n^2\log n) 的最小三角形算法，但是貌似有误）
计算几何 -- 算法与应用（第 2 版）
https://arxiv.org/pdf/1712.08911
https://www.sciencedirect.com/science/article/abs/pii/S092577212030136X
https://www.sciencedirect.com/science/article/pii/S1570866713000245#br0070
https://pub.ista.ac.at/~edels/Papers/1986-07-ArrangementsLinesHyperplanes.pdf