Empty-Ellipse Graphs

Olivier Devillers, Jeff G Erickson, Xavier Goaoc

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 IR 3. 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 empty-ellipse 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 l).

Original languageEnglish (US)
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages1249-1257
Number of pages9
StatePublished - Dec 1 2008
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: Jan 20 2008Jan 22 2008

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CitySan Francisco, CA
Period1/20/081/22/08

    Fingerprint

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Devillers, O., Erickson, J. G., & Goaoc, X. (2008). Empty-Ellipse Graphs. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1249-1257). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).