Embedding point sets into plane graphs of small dilation
(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:
https://lup.lub.lu.se/record/209594
- author
- Ebbers-Baumann, 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
- 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-06-03 21:29:58
@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 >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 = {{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}}, }