Embedding point sets into plane graphs of small dilation
(2005) 16th International Symposium, ISAAC 2005 In Algorithms and Computation / Lecture notes in computer science 3827. p.516 Abstract
 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 >= 2/root 3 approximate to... (More)
 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 >= 2/root 3 approximate to 1.1547. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/209594
 author
 EbbersBaumann, A; Grune, A; Karpinski, M; Klein, R; Knauer, C and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2005
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 geometric network, dilation, plane graph, lower bound, stretch factor, spanning ratio
 in
 Algorithms and Computation / Lecture notes in computer science
 volume
 3827
 pages
 5  16
 publisher
 Springer
 conference name
 16th International Symposium, ISAAC 2005
 external identifiers

 wos:000234885900003
 scopus:33744964834
 ISSN
 16113349
 03029743
 ISBN
 3540309357
 DOI
 10.1007/11602613_3
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 9b74d73a76ee4fc2adad7a0dac1de53d (old id 209594)
 date added to LUP
 20070810 11:46:02
 date last changed
 20170416 03:28:47
@inproceedings{9b74d73a76ee4fc2adad7a0dac1de53d, abstract = {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 >= 2/root 3 approximate to 1.1547.}, author = {EbbersBaumann, A and Grune, A and Karpinski, M and Klein, R and Knauer, C and Lingas, Andrzej}, booktitle = {Algorithms and Computation / Lecture notes in computer science}, isbn = {3540309357}, issn = {16113349}, keyword = {geometric network,dilation,plane graph,lower bound,stretch factor,spanning ratio}, language = {eng}, pages = {516}, publisher = {Springer}, title = {Embedding point sets into plane graphs of small dilation}, url = {http://dx.doi.org/10.1007/11602613_3}, volume = {3827}, year = {2005}, }