|
|
|
In the context of a diploma thesis at the university of Bonn we present an implementation of the deterministic algorithm for constructing a single face in an arrangement of line segments using CGAL´s arrangement package and its sweep line framework. The algorithm is developed and presented in the book “Davenport-Schinzel sequences and their geometric applications” by Micha Sharir and Pankaj K. Agarwal, Cambridge University Press, 1995. While the complexity of a full arrangement of line segments is in \(O(n^2)\), Sharir and Agarwal show that any single face in such arrangement has a maximum complexity of \(O(\alpha(n) \cdot n)\) where \(\alpha(n)\) denotes the extremely slow-growing inverse Ackermann function which can be regarded as constant for any conceivable real-world input. Any single face can be constructed in time \(O(α(n) \cdot n \cdot \log^2 n)\) using a deterministic divide and conquer algorithm including—in the words of Sharir and Agarwal—a “sophisticated sweep-line technique” in the merge step (“red blue merge”).