Empty-ellipse graphs
| Autor: | Olivier Devillers, Erickson, J., Goaoc, X. |
|---|---|
| Přispěvatelé: | Geometric computing (GEOMETRICA), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut National de Recherche en Informatique et en Automatique (Inria), Department. of Computer Science [Illinois], University of Illinois System, Effective Geometric Algorithms for Surfaces and Visibility (VEGAS), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2008 |
| Předmět: | |
| Zdroj: | 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08) 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 2008, San Francisco, United States. pp.1249--1256 Scopus-Elsevier |
| Popis: | International audience; 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). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|