On the geometric dilation of closed curves, graphs, and point sets

Simple item page
dc.creatorDumitrescu, Adrian
dc.creatorEbbers-Baumann, Annette
dc.creatorGrüne, Ansgar
dc.creatorKlein, Rolf
dc.creatorRote, Günter
dc.date2004-07-08
dc.date2005-08-25
dc.date.accessioned2026-07-07T08:53:05Z
dc.date.available2026-07-07T08:53:05Z
dc.descriptionThe 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.
dc.description31 pages, 16 figures. The new version is the extended journal submission; it includes additional material from a conference submission (ref. [6] in the paper)
dc.identifierhttps://arxiv.org/abs/math/0407135
dc.identifierhttp://arxiv.org/abs/math/0407135
dc.identifierComputational Geometry, Theory and Applications 36 (2006), 16-38
dc.identifierdoi:10.1016/j.comgeo.2005.07.004
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/145500
dc.subjectMetric Geometry
dc.subject51F99
dc.titleOn the geometric dilation of closed curves, graphs, and point sets
dc.typetext

Files

Collections

arXiv