inria-00338701, version 1
Computing Largest Circles Separating Two Sets of Segments
Jean-Daniel Boissonnat 1Jurek Czyzowicz a, 2Olivier Devillers
1Jorge Urrutia 3Mariette Yvinec
1
International Journal of Computational Geometry and Applications 10 (2000) 41--54
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 allowed to meet only at their endpoints. In the general case, when line segments may intersect Omega(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 the Ackermann function.
- a – Université du Québec à Hull
- 1 : PRISME (INRIA Sophia Antipolis)
- INRIA
- 2 : Departement d'Informatique et d'ingénierie [Québec]
- Université du Québec à Hull
- 3 : University of Ottawa
- University of Ottawa
- Domaine : Informatique/Géométrie algorithmique
- inria-00338701, version 1
- http://hal.inria.fr/inria-00338701
- oai:hal.inria.fr:inria-00338701
- Contributeur : Olivier Devillers
- Soumis le : Vendredi 14 Novembre 2008, 09:43:24
- Dernière modification le : Vendredi 14 Novembre 2008, 10:08:13