### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 1249-1257 |

Number of pages | 9 |

State | Published - Dec 1 2008 |

Event | 19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States Duration: Jan 20 2008 → Jan 22 2008 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 19th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | San Francisco, CA |

Period | 1/20/08 → 1/22/08 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Mathematics(all)

### Cite this

*Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 1249-1257). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).