6.8 附加练习
(Additional Exercises)
- 中心点 Centerpoints。对于有 \(n\) 个点的集合 \(P\)，如果每个包含 \(x\) 的半平面，也包含 \(P\) 中很大比例的点(为了精确起见，稍后定义)，
那么点 \(x\) 就被称为点集 \(P\) 的"中心点(centerpoint)"。点 \(x\) 不一定必须在 \(P\) 中。只是相对于 \(P\) 是"中心(central)"的。
在这个意义上，捕捉到中心点必然捕捉到 \(P\) 的很大一部分。形式化的定义是，如果不存在开半平面，不包含点 \(x\) 却包含 \(P\) 中超过\(\frac{2}{3}n\) 个点，
那么 \(x\) 是一个中心点(Edelsbrunner 1987, p. 64)。
- 通过探索所有四点集的配置，验证任何 \(n=4\) 个点的集合都有一个中心点。
- 从排列的层次角度解释“每个有限点集都有一个中心点”这一命题。
- 基于 (b) 提出一个寻找中心点的算法。
- 最小面积三角形 Minimum area triangle。
- 证明如果点 \(\{a, b, c\}\) 在给定的有限点集 \(P\) 中实现了面积最小的三角形，那么 \(c\) 是 \(P \setminus \{a, b\}\) 中距离包含 \(ab\) 的直线 \(L_{ab}\) 最近的点， 其中距离是沿 \(L_{ab}\) 的法线测量的。
- 在对偶的排列 \(A(P)\) 中解释这种关系。
- 利用这种关系设计一个算法，从平面上的 \(n\) 个点集 \(P\) 中选择顶点来寻找最小面积三角形。尝试优于暴力 \(O(n^3)\) 算法。
- 贪婪的圆点 Voracious circle points。给定 \(n\) 个点的集合 \(P = \{p_1, \dots, p_n\}\)，定义 \(\mu(p_i, p_j)\) 为任何包含 \(p_i\) 和 \(p_j\) 的闭圆盘中，
包含最少 \(P\) 的点。我们将在 \(P\) 中最大化 \(\mu\) 的点对，称为贪婪圆点对(voracious circle points)(Diaz 1990)。
称这个最大值为 \(M(P) = \max_{p_i, p_j \in P} \mu(p_i, p_j)\)。
- 对所有 \(n=3\) 个点的集合 \(P\) 确定 \(M(P)\)。
- 对所有 \(n=4\) 个点的集合 \(P\) 确定 \(M(P)\)。
- 证明，如果存在一个圆盘 \(D\) 包含 \(p_i\) 和 \(p_j\) 以及 \(P\) 中其他 \(k\) 个点， 那么存在一个圆盘 \(D' \subseteq D\)，其边界包含 \(p_i\) 和 \(p_j\)，并且包含 \(\le k\) 个 \(P\) 的点。
- 利用 (c) 来设计一个在固定 \(p_i\) 和 \(p_j\) 时计算 \(\mu(p_i, p_j)\) 的算法。
- 利用 (d) 设计一个寻找贪婪圆点对的算法。
- 四等分 Four-section。一个点集\(P\)的"四等分(four-section)"是指一对直线，该直线对形成的四个开楔形区域(open wedges)中每个区域内的点数dou不超过 \(\lceil n/4 \rceil\)。
- 论证每个有限点集都有一个四等分
- 设计一个四等分算法
- 正交四等分 Orthogonal four-section。设计一个算法，寻找一个点集的四等分，使得两条线是正交的(Diaz 1990)。