Stony Brook Algorithm Repository

Maintaining Line Arrangements


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:


cgal (rating 10)
Topological Sweep in Degenerate Cases (rating 9)
CGAL (rating 8)
Arrange (rating 7)
LEDA (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

Go To Main Page