The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.6.15 Maintaining Line Arrangements

Problem Input | Problem Output

INPUT                    OUTPUT

Input Description: A set of lines and line segments l_1,...,\l_n.

Problem: What is the decomposition of the plane defined by l_1,...,\l_n?

Excerpt from The Algorithm Design Manual: One of the most fundamental problems in computational geometry is constructing arrangements of lines, that is, explicitly building the regions formed by the intersections of a set of $n$ lines. Algorithms for a surprising number of problems are based on constructing and analyzing the arrangement of a specific set of lines:


  • Topological Sweep in Degenerate Cases (C++) (rating 9)
  • CGAL: The Computational Geometry Algorithms Library (C++) (rating 8)
  • Arrange - maintainance of arrangements with point location (C) (rating 7)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 4)

  • Recommended Books

    Davenport-Schinzel sequences and their geometric applications by M. Sharir and P. Agarwal Computational Geometry in C by Joseph O'Rourke Algorithms in Combinatorial Geometry by Herbert Edelsbrunner

    Related Problems

    Robust Geometric Primitives
    Intersection Detection
    Point Location

    This page last modified on 2008-07-10 .