Embedding point sets into plane graphs of small dilation
(2005) 16th International Symposium, ISAAC 2005 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:
https://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
 host publication
 Algorithms and Computation / Lecture notes in computer science
 volume
 3827
 pages
 5  16
 publisher
 Springer
 conference name
 16th International Symposium, ISAAC 2005
 conference location
 Sanya, Hainan, China
 conference dates
 20051219  20051221
 external identifiers

 wos:000234885900003
 scopus:33744964834
 ISSN
 03029743
 16113349
 ISBN
 3540309357
 DOI
 10.1007/11602613_3
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 9b74d73a76ee4fc2adad7a0dac1de53d (old id 209594)
 date added to LUP
 20160401 11:49:15
 date last changed
 20210309 04:31:49
@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 = {03029743}, 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}, doi = {10.1007/11602613_3}, volume = {3827}, year = {2005}, }