4.7 附加练习
(Additional Exercises)

1. 直径和宽度 Diameter and width。这是练习 3.9.3[3] 的推广。
   1. 构造一个具有 \(n\) 个顶点的多胞体，使其直径，任意两点之间的最大距离，由尽可能多的不同点对实现。
   2. 构造一个具有 \(n\) 个顶点的多胞体，使其拥有尽可能多的不同对趾点对(antipodal pairs)。对趾点是指能由平行的平面支撑的点， 平面只在支撑点出于多胞体有接触并将凸包置于平面的同一侧。
   3. 描述可能表示多胞体宽度的接触特征，其中宽度是平行支撑平面之间的最小距离。每个支撑平面可能接触一个面\(f\)，一条边\(e\)(但不是面)，或一个顶点\(v\)(但不是边)。 在 \((v, v), (v, e), (v, f), (e, e), (e, f), (f, f)\) 这六种可能的组合中，哪些可以描述宽度？

2. GEB。《Gödel, Escher, Bach》(Hofstadter 1979)的封面展示了一块实心的雕刻木头，它在三个正交方向上投射出字母"G"、"E"和"B"的影子。
   1. 是否所有的字母三元组都能作为某个实心、连通物体的影子来实现? 对字母的形状做任何合理的假设。如果是，请给出论证。如果不是，请展示无法相互实现的三元组。
   2. 给定三个正交多边形，设计一个算法来计算一个形状，其影子就是这些多边形，见图 4.22，或者报告不存在这样的形状。 尽量在高层面上描述算法，关注方法而非实现细节。分析算法的时间复杂度，写出关于多边形顶点数 \(n\) 的函数，假设它们都有大致相同数量的顶点。 讨论你的算法是否可以修改以处理非正交多边形；也许它不能。
3. 多胞体到四面体 Polytope to tetrahedra。对于一个有 \(V, E, F\) 个顶点、边和面的多胞体，当它被分割成四面体，所有四面体的边的端点都是多胞体的顶点，会产生多少个四面体 \(T\)? \(T\) 是否由 \(V, E, F\) 决定? 如果是，请提供公式；如果不是，请提供 \(T\) 的上下界。
4. 稳定多胞体Stable polytopes。设计一个算法来判断放置在给定面上的多胞体是稳定的还是会倾倒的(参见练习 1.6.8[5])。
5. 立方体表面的最短路径Shortest path on a cube's surface。设计一种方法，在立方体表面上找到两点 \(x\) 和 \(y\) 之间的最短路径，路径需位于表面上。 这就是苍蝇在 \(x\) 和 \(y\) 之间行走的最短路径。
6. 三角形 \(\cap\) 立方体Triangle \(\cap\) cube。在三维空间中，当一个三角形与一个立方体相交时，结果是一个多边形 \(P\)。 这是图形学中常见的一种计算，将三角形裁剪到立方体视景体(cubical viewing space)。对于三角形来说，\(P\) 可能拥有的最大顶点数是多少？
7. [Programming] 多面体的体积 Volume of a polyhedron。以类似于第 1 章中用于计算多边形面积的方式，计算多面体的体积。 选择一个任意点 \(p\)，例如，第 0 个顶点，计算由 \(p\) 和多面体的每个四面体形成的有符号体积，并将这些四面体体积相加。四面体体积的总和即为多面体的体积。
   输入多面体的格式如下，读入 \(V\)，即顶点数，然后是顶点的坐标。读入 \(F\)，即三角形面的数量，然后是三个顶点索引，每个面一组。