Search: onr:"swepub:oai:lup.lub.lu.se:7f6b3f7d-3a40-4334-9540-dd3c476f1c48" >
Embedding point set...
Embedding point sets into plane graphs of small dilation
-
Ebbers-Baumann, Annette (author)
-
Gruene, Ansgar (author)
-
Klein, Rolf (author)
-
show more...
-
Karpinski, Marek (author)
-
Knauer, Christian (author)
-
- Lingas, Andrzej (author)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
show less...
-
(creator_code:org_t)
- 2007
- 2007
- English.
-
In: International Journal of Computational Geometry and Applications. - 0218-1959. ; 17:3, s. 201-230
- Related links:
-
http://dx.doi.org/10...
-
show more...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- geometric network
- spanning ratio
- plane graph
- lower bound
- stretch factor
- dilation
Publication and Content Type
- art (subject category)
- ref (subject category)
Find in a library
To the university's database