The density of iterated crossing points and a gap result for triangulations of finite point sets
| dc.creator | Klein, Rolf | |
| dc.creator | Kutz, Martin | |
| dc.date | 2006-01-10 | |
| dc.date.accessioned | 2026-07-07T06:57:54Z | |
| dc.date.available | 2026-07-07T06:57:54Z | |
| dc.description | 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 in R^2, 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*. The main result of this paper is the following gap theorem: For any finite point set P in the plane for which the above P* is infinite, there exists a threshold t > 1 such that P is not contained in the vertex set of any finite plane graph of dilation at most t. We construct a concrete point set Q such that any planar graph that contains this set amongst its vertices must have a dilation larger than 1.0000047. | |
| dc.description | 10 pages + appendix | |
| dc.identifier | https://arxiv.org/abs/cs/0601033 | |
| dc.identifier | http://arxiv.org/abs/cs/0601033 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/107145 | |
| dc.subject | Computational Geometry | |
| dc.title | The density of iterated crossing points and a gap result for triangulations of finite point sets | |
| dc.type | text |