Computing a single cell in the union of two simple polygons

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 of two simple polygons in the plane.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00413170
Contributor : Olivier Devillers <>
Submitted on : Thursday, September 3, 2009 - 1:42:11 PM
Last modification on : Tuesday, August 13, 2019 - 10:16:02 AM
Long-term archiving on : Tuesday, June 15, 2010 - 11:08:06 PM

File

bdds-cscot-97.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Mark De Berg, Olivier Devillers, Katrin Dobrindt, Otfried Schwarzkopf. Computing a single cell in the union of two simple polygons. Information Processing Letters, Elsevier, 1997, 63, pp.215-219. ⟨10.1016/S0020-0190(97)00125-7⟩. ⟨inria-00413170⟩

Share

Metrics

Record views

327

Files downloads

314