Empty-ellipse graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Empty-ellipse graphs

Résumé

We define and study a geometric graph over points in the plane that captures the local behavior of Delaunay triangulations of points on smooth surfaces in 3-space. Two points in a planar point set P are neighbors in the empty-ellipse graph if they lie on an axis-aligned ellipse with no point of P in its interior. The empty-ellipse graph can be a clique in the worst case, but it is usually much less dense. Specifically, the emptyellipse graph of n points has complexity Θ(Δn) in the worst case, where Δ is the ratio between the largest and smallest pairwise distances. For points generated uniformly at random in a rectangle, the empty-ellipse graph has expected complexity Θ(n log n). As an application of our proof techniques, we show that the Delaunay triangulation of n random points on a circular cylinder has expected complexity Θ(n log n).
Fichier principal
Vignette du fichier
empty-ellipse-soda08.pdf (292.67 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00176204 , version 1 (02-10-2007)

Identifiants

  • HAL Id : inria-00176204 , version 1

Citer

Olivier Devillers, Jeff Erickson, Xavier Goaoc. Empty-ellipse graphs. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 2008, San Francisco, United States. pp.1249--1256. ⟨inria-00176204⟩
262 Consultations
137 Téléchargements

Partager

Gmail Facebook X LinkedIn More