# Computing a single face in an arrangement of line segments

### Abstract

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(α(

*n*)*

*n*) where α(

*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*)*

*n**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").

^{}### Links

- https://github.com/janniswarnat/Red_blue_merge_demo
- Jannis Warnat
**Computing a single face in an arrangement of line segments with CGAL**,

M.Sc. thesis, Rheinische Friedrich-Wilhelms-Universität Bonn,Institut für Informatik I, August, 2009.

### Contact

Jannis Warnat |