The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

Arrange - maintainance of arrangements with point location

Arrange is a package written in C by Michael Goldwasser of Stanford University for maintaining arrangements of polygons in either the plane or on the sphere. Polygons may be degenerate, and hence represent arrangements of lines. A randomized incremental construction algorithm is used, and efficient point location on the arrangement supported. Polygons may be inserted but not deleted from the arrangement, and arrangements of several thousand vertices and edges can be constructed in a few seconds. Arrange is available from ftp://robotics.stanford.edu/pub/wass/arrangement.
  • Download Files (local site)
  • Michael Goldwasser's Site
  • List of files
  • Paper in PDF

    Problem Links
    Maintaining Line Arrangements (7)
    Point Location (5)


    This page last modified on 2008-07-10 .
    www.algorist.com