Computing a Single Cell in the Union of two Simple Polygons

1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
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$.)
Keywords :
Document type :
Reports
Domain :

https://hal.inria.fr/inria-00074061
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 2:24:42 PM
Last modification on : Saturday, January 27, 2018 - 1:31:27 AM
Long-term archiving on: : Monday, April 5, 2010 - 12:04:05 AM

Identifiers

• HAL Id : inria-00074061, version 1

Citation

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⟩

Record views