Embedding point sets into plane graphs of small dilation
(2007) In International Journal of Computational Geometry and Applications 17(3). p.201-230- 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 in to 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 in to 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/969071
- author
- Ebbers-Baumann, Annette ; Gruene, Ansgar ; Klein, Rolf ; Karpinski, Marek ; Knauer, Christian and Lingas, Andrzej LU
- organization
- publishing date
- 2007
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- geometric network, spanning ratio, plane graph, lower bound, stretch factor, dilation
- in
- International Journal of Computational Geometry and Applications
- volume
- 17
- issue
- 3
- pages
- 201 - 230
- publisher
- World Scientific Publishing
- external identifiers
-
- wos:000251155800002
- scopus:34347339313
- ISSN
- 0218-1959
- DOI
- 10.1142/S0218195907002318
- project
- VR 2005-4085
- language
- English
- LU publication?
- yes
- id
- 7f6b3f7d-3a40-4334-9540-dd3c476f1c48 (old id 969071)
- date added to LUP
- 2016-04-01 15:20:54
- date last changed
- 2022-01-28 04:54:13
@article{7f6b3f7d-3a40-4334-9540-dd3c476f1c48,
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 in to 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, Annette and Gruene, Ansgar and Klein, Rolf and Karpinski, Marek and Knauer, Christian and Lingas, Andrzej}},
issn = {{0218-1959}},
keywords = {{geometric network; spanning ratio; plane graph; lower bound; stretch factor; dilation}},
language = {{eng}},
number = {{3}},
pages = {{201--230}},
publisher = {{World Scientific Publishing}},
series = {{International Journal of Computational Geometry and Applications}},
title = {{Embedding point sets into plane graphs of small dilation}},
url = {{http://dx.doi.org/10.1142/S0218195907002318}},
doi = {{10.1142/S0218195907002318}},
volume = {{17}},
year = {{2007}},
}