TY - GEN

T1 - Empty-Ellipse Graphs

AU - Devillers, Olivier

AU - Erickson, Jeff G

AU - Goaoc, Xavier

PY - 2008/12/1

Y1 - 2008/12/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=58449116078&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58449116078&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449116078

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1249

EP - 1257

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -