In Proceedings of the 11th Symposium on Computational Geometry (SoCG), Vancouver, British Columbia, June 1995, pp. C32-33.

Available as: [ pdf, pdf.gz, ps, ps.Z, ps.gz , Sourcecode ]

An Implementation for Maintaing Arrangements of Polygons

by Michael Goldwasser

Abstract: Constructing arrangements of geometric objects is a basic problem in computational geometry. Applications relying on arrangements arise in such fields as robotics, assembly planning, computer vision, graphics, and computer-assisted surgery. Arrangements are also used as a building block for other theoretical results in computational geometry. Many papers and textbooks have presented algorithms for maintaining arrangements under various conditions.

This paper is a discussion of the practical issues that arose during the development of a software package which constructs an arrangement of polygons and segments using a basic randomized incremental approach. The need to handle polygons in addition to segments, and to deal with arrangements on a sphere as well as a plane, guided many design decisions. Also the need to cope with degeneracies and numerical inaccuracy in an efficient and consistent manner, brought up issues that are often glossed over in theoretical presentations of algorithms.

Michael Goldwasser