inria-00073985, version 1
Computing Largest Circles Separating Two Sets of Segments
Jean-Daniel Boissonnat
1Jurek CzyzowiczOlivier Devillers
Jorge UrrutiaMariette Yvinec
N° RR-2705 (1995)
Résumé : A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased while still separating the two given sets. An $\Theta(n \log n)$ optimal algorithm is proposed to find all largest circles separating two given sets of line segments when line segments are allow ed to meet only at their endpoints. This settles an open problem from a previous paper\cite{bcdy-csp-95}. In the general case, when line segments may intersect $Ømega(n^2)$ times, our algorithm can be adapted to work in $O(n \alpha(n) \log n)$ time and $O(n \alpha(n))$ space, where $\alpha(n)$ represents the extremely slowly growing inverse of Ackermann function.
- 1 : PRISME (INRIA Sophia Antipolis)
- INRIA
- Domaine : Informatique/Autre
- Mots-clés : COMPUTATIONAL GEOMETRY / SEPARABILITY
- Référence interne : RR-2705
- inria-00073985, version 1
- http://hal.inria.fr/inria-00073985
- oai:hal.inria.fr:inria-00073985
- Contributeur : Rapport De Recherche Inria
- Soumis le : Mercredi 24 Mai 2006, 14:14:35
- Dernière modification le : Mercredi 31 Mai 2006, 14:24:28






Documents associés

Exporter