Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound > 1. In this paper we provide the first upper and lower bounds for the embedding problem.

1. Each finite point set can be embedded into the vertex set of a finite triangulation of dilation ≤ 1.1247.

2. Each embedding of a closed convex curve has dilation ≥ 1.00157.

3. Let P be the plane graph that results from intersecting n infinite families of equidistant, parallel lines in general position. Then the vertex set of P has dilation .

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

P. Agarwalet al., Discrete Comput. Geom. (2006). Google Scholar
T. M. Apostol, Dirichlet Series in Number Theory, 2nd edn. (Springer-Verlag, 1997) pp. 148–155. Google Scholar
S. R. Arikatiet al., European Symp. Algorithms 514 (1996). Google Scholar
G. Das and D. Joseph, Which triangulations approximate the complete graph, Proc. Int. Symp. Optimal Algorithms, LNCS 401 (Springer, 1989) pp. 168–192. Google Scholar
D. P. Dobkin, S. J. Friedman and K. J. Supowit, Discr. Comput. Geom. 5, 399 (1990). Crossref, Web of Science, Google Scholar
A. Dumitrescu et al. , Comput. Geom.: Th. Appl. . Google Scholar
A. Dumitrescu, A. Ebbers-Baumann, A. Grüne, R. Klein and G. Rote, 9th Int. Workshop, WADS 2005, Waterloo, in eds. F. Dehne, A. López-Ortiz and J.-R. Sack, Algorithms and Data Structures, Proc. (Springer-Verlag, 2005), LNCS 3608, pp. 244–255 . Google Scholar
A. Ebbers-Baumann, A. Grüne and R. Klein, On the geometric dilation of finite point sets, 14th Int. Symp. ISAAC 2003, Kyoto, eds. T. Ibaraki, N. Katoh and H. Ono, Algorithms and Computation, Proceedings (Springer-Verlag, 2003), LNCS 2906, pp. 250–259; Journal Version: Algorithmica 44 (2006) 137–149 . Google Scholar
A. Ebbers-Baumann , A. Grüne and R. Klein , Comput. Geom.: Th. Appl. . Google Scholar
A. Ebbers-Baumannet al., Comput. Geom.: Th. Appl. 27, 123 (2004). Crossref, Web of Science, Google Scholar
D. Eppstein, Handbook of Computational Geometry, eds. J.-R. Sack and J. Urrutia (Elsevier, 1999) pp. 425–461. Google Scholar
D. Eppstein , The Geometry Junkyard ( ) , http://www.ics.uci.edu/eppstein/junkyard/dilation-free/ . Google Scholar
D. Eppstein and D. Hart, Shortest paths in an arrangement with k line orientations, Proc. 10th Ann. ACM-SIAM Symp. Discrete Algorithms (1999) pp. 310–316. Google Scholar
S. Fekete , R. Klein and A. Nüchter , Online searching with an autonomous robot , Workshop on Algorithmic Foundations of Robotics ( 2004 ) . Google Scholar
E. Hlawka, Theorie der Gleichverteilung, BI Wissenschaftsverlag . Google Scholar
J. M. Keil and C. A. Gutwin, Discr. Comput. Geom. 7, 13 (1992). Crossref, Web of Science, Google Scholar
R. Klein and M. Kutz, The density of iterated crossing points and a gap result for triangulations of finite point sets, Proc. 22nd Symp. Computational Geometry pp. 264–272. Google Scholar
D. Lorenz, On the dilation of finite point sets, Diploma Thesis, Bonn, 2005 . Google Scholar
G. Narasimhan and M. Smid , Geometric Spanner Networks ( Cambridge University Press ) . Google Scholar