Computing Largest Circles Separating Two Sets of Segments

Abstract : 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.
Type de document :
Communication dans un congrès
8th Canadian Conference on Computational Geometry, 1996, Ottawa, Canada. 〈http://www.cccg.ca/proceedings/1996/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01179145
Contributeur : Olivier Devillers <>
Soumis le : mercredi 22 juillet 2015 - 16:02:41
Dernière modification le : jeudi 11 janvier 2018 - 16:45:55

Identifiants

  • HAL Id : hal-01179145, version 1

Collections

Citation

Jean-Daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Jorge Urrutia, Mariette Yvinec. Computing Largest Circles Separating Two Sets of Segments. 8th Canadian Conference on Computational Geometry, 1996, Ottawa, Canada. 〈http://www.cccg.ca/proceedings/1996/〉. 〈hal-01179145〉

Partager

Métriques

Consultations de la notice

433