Embedding point sets into plane graphs of small dilation

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.

Gruene, Ansgar (författare)
Klein, Rolf (författare)
Karpinski, Marek (författare)
Knauer, Christian (författare)
Lingas, AndrzejLund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science(Swepub:lu)cs-ali (författare)
Data VetenskapNaturvetenskapliga fakulteten (creator_code:org_t)

Ingår i:International Journal of Computational Geometry and Applications17:3, s. 201-2300218-1959

Av författaren/redakt...: Ebbers-Baumann, ...; Gruene, Ansgar; Klein, Rolf; Karpinski, Marek; Knauer, Christia ...; Lingas, Andrzej

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.