Stony Brook Algorithm Repository


Maintaining Line Arrangements

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:


Implementations

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