Mathematics – Metric Geometry
Scientific paper
2004-07-08
Computational Geometry, Theory and Applications 36 (2006), 16-38
Mathematics
Metric Geometry
31 pages, 16 figures. The new version is the extended journal submission; it includes additional material from a conference su
Scientific paper
10.1016/j.comgeo.2005.07.004
The detour between two points u and v (on edges or vertices) of an embedded planar graph whose edges are curves is the ratio between the shortest path in in the graph between u and v and their Euclidean distance. The maximum detour over all pairs of points is called the geometric dilation. Ebbers-Baumann, Gruene and Klein have shown that every finite point set is contained in a planar graph whose geometric dilation is at most 1.678, and some point sets require graphs with dilation at least pi/2 = 1.57... We prove a stronger lower bound of 1.00000000001*pi/2 by relating graphs with small dilation to a problem of packing and covering the plane by circular disks. The proof relies on halving pairs, pairs of points dividing a given closed curve C in two parts of equal length, and their minimum and maximum distances h and H. Additionally, we analyze curves of constant halving distance (h=H), examine the relation of h to other geometric quantities and prove some new dilation bounds.
Dumitrescu Adrian
Ebbers-Baumann Annette
Grüne Ansgar
Klein Rolf
Rote Günter
No associations
LandOfFree
On the geometric dilation of closed curves, graphs, and 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 On the geometric dilation of closed curves, graphs, and point sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the geometric dilation of closed curves, graphs, and point sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-222502