Computing a Single Cell in the Union of two Simple Polygons - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 1995

Computing a Single Cell in the Union of two Simple Polygons

Olivier Devillers
Katrin Dobrindt
  • Fonction : Auteur
Otfried Schwarzkopf
  • Fonction : Auteur

Résumé

This note presents a non trivial combination of two techniques previously used with randomized incremental algorithms: the lazy cleaning scheme \cite{bds-lric-94} to maintain structures with `non local' definition and the $O(n\log^{\star}n)$ acceleration when some additional information about the data is known \cite{s-sfira-91,cct-rpatd-92,d-rysoa-92}. Authors assume that the reader is somehow familiar with this techniques. If, we are interested in computing a single face in the intersection of two simple polygons, the two previous techniques can be used. The lazy approach allows to compute a single face in an arrangement of line segments in expected time $O(n\alpha(n)\log n)$ but this technique do not exploit the organization of the segments in simple polygons. The accelerated framework compute the whole intersection of the two simple polygon in $O(n\log^{\star}n+A)$ where $A=O(n^2)$ is the number of intersection points, and then the relevant connected component can be extracted easily in $O(n)$ time. The two techniques can be combined to reach an algorithm whose expected time complexity is $O(n\log^{\star 2}n)$ which improve previous bounds above. {\scriptsize ( We denote by $\alpha(n)$ the pseudo-inverse of Ackermann function~; $\alpha$ grows to infinity, but excessively slow, for $n \leq 2^{2^{2^{\cdot^{\cdot^{\cdot^2}}}} \!\!\!\! \!\!\!{\swarrow^{\!\!\!\!\nearrow} 2^{65536}}}$ $\alpha(n) \leq 3$. We denote by $\log^{(i)}n= øverbrace{\log\log\ldots\log}^{\mbox{$i$ times}}n$; $\log^{\s- tar} n= \mbox{inf} {k; \log^{(k)}n \leq 1}$ and $(\log^{\star}n)^2$ by $\log^{\star 2}n$.\ Thus for any imaginable data set $n\leq 2^{65532}$ and thus $\log^{\star} n \leq 5$.)

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-2626.pdf (213.85 Ko) Télécharger le fichier

Dates et versions

inria-00074061 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00074061 , version 1

Citer

Mark de Berg, Olivier Devillers, Katrin Dobrindt, Otfried Schwarzkopf. Computing a Single Cell in the Union of two Simple Polygons. RR-2626, INRIA. 1995. ⟨inria-00074061⟩
156 Consultations
67 Téléchargements

Partager

Gmail Facebook X LinkedIn More