Search: onr:"swepub:oai:lup.lub.lu.se:7f6b3f7d-3a40-4334-9540-dd3c476f1c48" >
Embedding point set...
-
Ebbers-Baumann, Annette
(author)
Embedding point sets into plane graphs of small dilation
- Article/chapterEnglish2007
Publisher, publication year, extent ...
Numbers
-
LIBRIS-ID:oai:lup.lub.lu.se:7f6b3f7d-3a40-4334-9540-dd3c476f1c48
-
https://lup.lub.lu.se/record/969071URI
-
https://doi.org/10.1142/S0218195907002318DOI
Supplementary language notes
-
Language:English
-
Summary in:English
Part of subdatabase
Classification
-
Subject category:art swepub-publicationtype
-
Subject category:ref swepub-contenttype
Notes
-
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 and genre
Added entries (persons, corporate bodies, meetings, titles ...)
-
Gruene, Ansgar
(author)
-
Klein, Rolf
(author)
-
Karpinski, Marek
(author)
-
Knauer, Christian
(author)
-
Lingas, AndrzejLund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science(Swepub:lu)cs-ali
(author)
-
Data VetenskapNaturvetenskapliga fakulteten
(creator_code:org_t)
Related titles
-
In:International Journal of Computational Geometry and Applications17:3, s. 201-2300218-1959
Internet link
Find in a library
To the university's database