Personal tools
You are here: Home Projects External Projects Computing a single face in an arrangement of line segments with CGAL Computing a single face in an arrangement of line segments
« April 2017 »
April
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
30
Log in


Forgot your password?
 

Computing a single face in an arrangement of line segments


An unbounded face


The unbounded single face (purple) of the given arrangement; in this instance the boundary consists of several connected components



Another unbounded single face


The unbounded single face of a random arrangement


Abstract

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(n2), 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*log2n) 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

  • http://www.divshare.com/folder/671600-80a
  • 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 jannis.warnat@gmx.de
Document Actions