Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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 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
; ; ; ; and
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
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
2005-12-19 - 2005-12-21
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
2016-04-01 11:49:15
date last changed
2024-01-07 21:44:56
@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}},
  keywords     = {{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}},
  doi          = {{10.1007/11602613_3}},
  volume       = {{3827}},
  year         = {{2005}},
}