Skip to Main content Skip to Navigation
Conference papers

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).
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download
Contributor : Xavier Goaoc <>
Submitted on : Tuesday, October 2, 2007 - 6:53:13 PM
Last modification on : Thursday, August 1, 2019 - 2:13:44 PM
Document(s) archivé(s) le : Monday, September 24, 2012 - 1:01:34 PM


Files produced by the author(s)


  • HAL Id : inria-00176204, version 1



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⟩



Record views


Files downloads