6.1 介绍
(Introduction)
直线和平面的排列是计算几何中第三个重要结构，其重要性不亚于凸包和维诺图。正如我们在上一章末尾瞥见的， 并且将在6.6节中详细讨论，这三种结构密切相关。图 6.1 显示了一个直线排列。 它是平面上一组直线的排列，直线的数量可以是无限的。这些直线将平面划分为若干凸区域(convex regions, 也称为 cells 或者 faces)，直线交叉点之间构成了线段或边，直线相交处为顶点。 图中的示例有 \(V = 45\) 个顶点、\(E = 100\) 条边和 \(F = 56\) 个面。并非所有这些都在图的有限窗口内可见。正是这种划分被称为排列(arrangement)。 通常我们将面视为开集，既，不包含它的边。将边视为开线段，既，不包括其边界顶点。这样划分就是一个真正的划分(a true partition): 它的碎片覆盖整个平面，但这些碎片彼此不相交， 数学家们更喜欢说它们是"两两不相交(pairwise disjoint)"的。
排列可能看起来过于抽象而没有太大的实用性，但实际上它们出现在各种各样的上下文中。这里有四个，更多的将在6.7 节中讨论。
- 可见性图 Visibility Graphs
设 \(S\) 为一组包含 \(n\) 个不相交线段的集合，且其中任意三个端点不共线。端点可见性图(endpoint visibity graph)中对应每个端点都有一个节点， 并且如果开线段 \((x, y)\) 不接触 \(S\) 中的任何线段，就在端点 \(x\) 和 \(y\) 之间连接一条弧，表示，\(x\) 和 \(y\) 可以清晰地看见对方。 通常，线段本身的弧也包含在图中。正如在第8章(8.2节)中将看到该图在机器人技术中的应用。 构建此图的一种朴素算法的复杂度为 \(O(n^3)\)，因为对于每一对 \(x\) 和 \(y\)，都需要花费 \(O(n)\) 的时间来检查所有线段是否与 \((x, y)\) 相交。 利用排列可以将复杂度降低至 \(O(n^2)\)(O'Rourke 1987，pp.211-17)。 - 消除隐藏面 Hidden Surface Removal
消除隐藏面主要是在计算三维场景中哪些表面从视点看是被遮挡，并利用这些信息构建二维图形图像的过程。第一个最坏情况下最优的 \(\Theta(n^2)\) 算法就依赖排列(McKenna 1987) (见6.7.2节)。 - 空凸多边形 Empty Convex Polygons
给定平面上的一组 \(n\) 个点，寻找顶点取自 \(S\) 的最大空凸多边形(largest empty convex polygon)。这里"最大(largest)"意味着拥有最多的顶点。 这个问题受到 Erdős 提出的一个未解决问题的启发，目前尚不清楚是否每一个足够大的点集都必须包含一个空六边形(Horton 1983)。 利用排列，可以在 \(O(n^3)\) 时间内找到最大的空凸多边形(Edelsbrunner & Guibas 1989; Dobkin, Edelsbrunner & Overmars 1990)。 - 切割火腿三明治 Ham-Sandwich Cuts
这是一个意义非凡的定理，任何火腿奶酪三明治都可以被一个平面切开，使得两半拥有完全相同量的面包、火腿和奶酪! 该定理的二维版本意味着， 总是存在一条直线可以同时平分两个点集。排列允许在与集合大小成线性的时间内找到这种平分线(见6.7.6节)。
本章将阐述直线排列的基本原理，但不会深入探讨上述四种应用。我的目标是概述要点，详细内容留给其他资料参考。本章不包含任何实现示例，并且由于其抽象程度较高，可能是本书中最具挑战性的章节。