English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

The Density of Iterated Crossing Points and a Gap Result for Triangulations of Finite Point Sets

MPS-Authors
/persons/resource/persons44874

Kutz,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Klein, R., & Kutz, M. (2006). The Density of Iterated Crossing Points and a Gap Result for Triangulations of Finite Point Sets. In Proceedings of the 22nd Annual Symposium on Computational Geometry, SCG'06 (pp. 264-272). New York, NY, USA: ACM.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2492-4
Abstract
Consider a plane graph G, drawn with straight lines. For every pair a,b of vertices of G, we compare the shortest-path distance between a and b in G (with Euclidean edge lengths) to their actual distance in the plane. The worst-case ratio of these two values, for all pairs of points, is called the dilation of G . All finite plane graphs of dilation 1 have been classified. They are closely related to the following iterative procedure. For a given point set P ⊆ R2, we connect every pair of points in P by a line segment and then add to P all those points where two such line segments cross. Repeating this process infinitely often, yields a limit point set P∞⊇P. This limit set P∞ is finite if and only if P is contained in the vertex set of a triangulation of dilation 1.The main result of this paper is the following gap theorem: For any finite point set P in the plane for which P∞ is infinite, there exists a threshold λ > 1 such that P is not contained in the vertex set of any finite plane graph of dilation at most λ. As a first ingredient to our proof, we show that such an infinite P∞ must lie dense in a certain region of the plane. In the second, more difficult part, we then construct a concrete point set P0 such that any planar graph that contains this set amongst its vertices must have a dilation larger than 1.0000047.