Computing a Single Cell in the Union of two Simple Polygons

Abstract : 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$.)
Type de document :
RR-2626, INRIA. 1995
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:24:42
Dernière modification le : samedi 27 janvier 2018 - 01:31:27
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:04:05



  • HAL Id : inria-00074061, version 1



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〉



Consultations de la notice


Téléchargements de fichiers