Advanced

Embedding point sets into plane graphs of small dilation

Ebbers-Baumann, A; Grune, A; Karpinski, M; Klein, R; Knauer, C and Lingas, Andrzej LU (2005) 16th International Symposium, ISAAC 2005 In Algorithms and Computation / Lecture notes in computer science 3827. p.5-16
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:
author
organization
publishing date
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
1611-3349
0302-9743
ISBN
3-540-30935-7
DOI
10.1007/11602613_3
project
VR 2002-4049
language
English
LU publication?
yes
id
9b74d73a-76ee-4fc2-adad-7a0dac1de53d (old id 209594)
date added to LUP
2007-08-10 11:46:02
date last changed
2017-04-16 03:28:47
@inproceedings{9b74d73a-76ee-4fc2-adad-7a0dac1de53d,
  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 &gt;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 &lt;= 1.1247. 2. Each embedding of a closed convex curve has dilation &gt;= 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 &gt;= 2/root 3 approximate to 1.1547.},
  author       = {Ebbers-Baumann, 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         = {3-540-30935-7},
  issn         = {1611-3349},
  keyword      = {geometric network,dilation,plane graph,lower bound,stretch factor,spanning ratio},
  language     = {eng},
  pages        = {5--16},
  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},
}