Edge-Skeletons in Arrangements with Applications

An edge-skeleton in an arrangement A(H) of a finite set of planes in E(3) is a connected collection of edges in A(H). We give a method that constructs a skeleton in O(root n log n) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams in E(2) and space cutting trees in E(3). We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.