Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Embedding point sets into plane graphs of small dilation

In English

Författare

  • A Ebbers-Baumann
  • A Grune
  • M Karpinski
  • R Klein
  • C Knauer
  • Andrzej Lingas

Summary, in English

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.

Avdelning/ar

  • Computer Science

Publiceringsår

2005

Språk

Engelska

Sidor

5-16

Publikation/Tidskrift/Serie

Algorithms and Computation / Lecture notes in computer science

Volym

3827

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Computer Science

Nyckelord

  • geometric network
  • dilation
  • plane graph
  • lower bound
  • stretch factor
  • spanning ratio

Conference name

16th International Symposium, ISAAC 2005

Conference date

2005-12-19 - 2005-12-21

Conference place

Sanya, Hainan, China

Status

Published

Projekt

  • VR 2002-4049

ISBN/ISSN/Övrigt

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 3-540-30935-7