Computing Largest Circles Separating Two Sets of Segments - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 1995

Computing Largest Circles Separating Two Sets of Segments

Jean-Daniel Boissonnat
  • Fonction : Auteur
  • PersonId : 830857
Jurek Czyzowicz
  • Fonction : Auteur
Olivier Devillers
Jorge Urrutia
  • Fonction : Auteur
Mariette Yvinec

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-2705.pdf (232.99 Ko) Télécharger le fichier

Dates et versions

inria-00073985 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00073985 , version 1

Citer

Jean-Daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Jorge Urrutia, Mariette Yvinec. Computing Largest Circles Separating Two Sets of Segments. RR-2705, INRIA. 1995. ⟨inria-00073985⟩
94 Consultations
128 Téléchargements

Partager

Gmail Facebook X LinkedIn More