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:

The best book available for this problem is Algorithms in Combinatorial Geometry by Herbert Edelsbrunner.


Implementations

  • Arrange - maintainance of arrangements with point location (C) (rating 9)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)

    Related Problems

  • Robust Geometric Primitives
  • Intersection Detection
  • Point Location


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .