Empty-ellipse graphs

Olivier Devillers 1, 2 Jeff Erickson 3 Xavier Goaoc 4
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
4 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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).
Type de document :
Communication dans un congrès
19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 2008, San Francisco, United States. pp.1249--1256, 2008
Liste complète des métadonnées


https://hal.inria.fr/inria-00176204
Contributeur : Xavier Goaoc <>
Soumis le : mardi 2 octobre 2007 - 18:53:13
Dernière modification le : mardi 25 octobre 2016 - 16:59:58
Document(s) archivé(s) le : lundi 24 septembre 2012 - 13:01:34

Fichier

empty-ellipse-soda08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00176204, version 1

Collections

Citation

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, 2008. <inria-00176204>

Partager

Métriques

Consultations de
la notice

419

Téléchargements du document

124