6.4 三维及更高维空间
(Three and Higher Dimensions)
排列理论最优美的方面之一是，几乎每一个特征都能平滑地推广到更高维度。虽然我们将不会详细讨论这个话题，但定理6.2.1、 6.2.2 和 6.3.1 的推广形式还是值得一提的：
定理 6.4.1. 在 \(d\) 维空间中，超平面排列的任意维度的面数为 \(O(n^d)\)，任意超平面的区域(zone)的总复杂度为 \(O(n^{d-1})\)， 并且这种排列可以在 \(O(n^d)\) 的时间和空间内构建。
特别地，三维空间中平面排列的复杂度为 \(O(n^3)\)，并且可以在此时间内构建，这一事实我们将在 6.6 节和 6.7 节中使用。
6.4.1. 练习
- 插入更新 Insertion updates。论证如果排列由双生边(twin-edge)数据结构表示，那么插入一条新线引起的更新可以在 \(O(n)\) 时间内完成。
- 线束，平面束 Pencil of lines, planes。
- 由 \(n\) 条线组成的线束形成的排列中有多少个顶点、边和面?
- 由 \(n\) 个共享一个公共点的平面形成的排列中有多少个顶点、边、面和 3-cell?