Edge-skeletons in arrangements with applications (Q1091825)

The paper gives a method for constructing general edge-skeletons in three-dimensional arrangements of planes. Here, an edge-skeleton is a connected subset of the edges in this arrangement. This problem is not interesting per se but it has a number of applications, such as constructing Voronoi diagrams and power diagrams of arbitrary order in the plane or constructing space cutting trees in three dimensions. Indeed, whenever a problem can be mapped to an arrangement problem for three-dimensional planes, the presented algorithm can be used to compute a solution. In Section 4 of the paper the author describes a technique that consistently treats all degenerate cases such as four planes through a common point, etc. This technique allows the author to ignore all special cases when he implements the main part of the algorithm - those cases are taken care of in the lowest level of the implementation, that is, the procedures that provide the primitive geometric operations. This technique is general enough to be of substantial help for the implementation of many other geometric algorithms.