Computer Science – Computational Geometry
Scientific paper
2006-01-10
Computer Science
Computational Geometry
10 pages + appendix
Scientific paper
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.
Klein Rolf
Kutz Martin
No associations
LandOfFree
The density of iterated crossing points and a gap result for triangulations of finite point sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The density of iterated crossing points and a gap result for triangulations of finite point sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The density of iterated crossing points and a gap result for triangulations of finite point sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-214213