Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

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

MPG-Autoren
/persons/resource/persons44874

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-2492-4
Zusammenfassung
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.