computational-geometry - 给定一个 DCEL，其中孪生等于边的下一个，细分可以有多少个面？

Question

我正在尝试解决“计算几何 - 算法和应用”一书中的练习 2.7（由 Berg 等人撰写），它说

给定一个细分的双连接边列表表示，其中 Twin(e) = Next(e) 对于每个半边 e 成立，那么细分最多可以有多少个面？

我认为解决方案是只连接两个顶点的边，下一个可能是双子。所以，唯一的脸可能是无限脸。它们可以是由一条边连接的更多对顶点，但前提是它们在每个顶点上是不相交的。还有其他可能性吗？

Answer 1

我会说你是对的。

假定对于所有半边 e，Next(e) 等于 Twin(e)，则 IncidentFace(Next(e)) 等于 IncidentFace(Twin(e))。并且由于我们知道 IncidentFace(e) 始终等于 IncidentFace(Next(e))，因此我们可以得出结论，对于所有半边， IncidentFace(e) 等于 IncidentFace(Twin(e))。所以没有边位于两个不同面的边界上。如果没有边限定两个不同的面，则不能有多个面。