s'authentifier
version française rss feed

inria-00074061, version 1

Computing a Single Cell in the Union of two Simple Polygons

Mark De Berg 1, Olivier Devillers (), Katrin Dobrindt, Otfried Schwarzkopf

N° RR-2626 (1995)

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$.)

  • Domaine : Informatique/Autre
  • Mots-clés : RANDOMIZED ALGORITHMS / COMPUTATIONAL GEOMETRY / ARRANGEMENT / TRAPEZOIDAL MAP
  • Référence interne : RR-2626
 
  • inria-00074061, version 1
  • oai:hal.inria.fr:inria-00074061
  • Contributeur : 
  • Soumis le : Mercredi 24 Mai 2006, 14:24:42
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:28
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...