Computing a single cell in the union of two simple polygons - Archive ouverte HAL Access content directly
Journal Articles Information Processing Letters Year : 1997

Computing a single cell in the union of two simple polygons

(1) , (2) , (1) , (1)
1
2

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.

Domains

Computer Science [cs] Computational Geometry [cs.CG]
Fichier principal
Vignette du fichier
bdds-cscot-97.pdf (183.56 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Olivier Devillers  : Connect in order to contact the contributor

https://hal.inria.fr/inria-00413170

Submitted on : Thursday, September 3, 2009-1:42:11 PM

Last modification on : Friday, February 4, 2022-3:11:11 AM

Long-term archiving on: Tuesday, June 15, 2010-11:08:06 PM

Download

Dates and versions

inria-00413170 , version 1 (03-09-2009)

Identifiers

Cite

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

Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

Collections

INRIA INRIA2
205 View
65 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More