Computing a single cell in the overlay of two simple polygons
Files
Publication date
1997
Authors
Berg, M. de
Devillers, O.
Dobrindt, K.T.G.
Schwarzkopf, O.
Editors
Advisors
Supervisors
DOI
Document Type
Preprint
Metadata
Show full item recordCollections
License
Abstract
This note combines the lazy randomized incremental construction
scheme with the technique of \connectivity acceleration" to obtain
an O ( n (log ? n ) 2 ) time randomized algorithm to compute a single
face in the overlay oftwo simple polygons in the plane.
Keywords
computational geometry, randomized algorithms, arrangement.