License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.34
URN: urn:nbn:de:0030-drops-121920
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12192/
Go to the corresponding LIPIcs Volume Portal

Dennis, Michael ; Perković, Ljubomir ; Türkoğlu, Duru

The Stretch Factor of Hexagon-Delaunay Triangulations

pdf-format:
LIPIcs-SoCG-2020-34.pdf (0.6 MB)

Abstract

The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch factor) of a Delaunay triangulation is one of the longstanding open problems in computational geometry. Over the years, a series of upper and lower bounds on the exact stretch factor have been obtained but the gap between them is still large. An alternative approach to solving the problem is to develop techniques for computing the exact stretch factor of "easier" types of Delaunay triangulations, in particular those defined using regular-polygons instead of a circle. Tight bounds exist for Delaunay triangulations defined using an equilateral triangle and a square. In this paper, we determine the exact stretch factor of Delaunay triangulations defined using a regular hexagon: It is 2. We think that the main contribution of this paper are the two techniques we have developed to compute tight upper bounds for the stretch factor of Hexagon-Delaunay triangulations.

BibTeX - Entry

@InProceedings{dennis_et_al:LIPIcs:2020:12192,
  author =	{Michael Dennis and Ljubomir Perković and Duru T{\"u}rkoğlu},
  title =	{{The Stretch Factor of Hexagon-Delaunay Triangulations}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12192},
  URN =		{urn:nbn:de:0030-drops-121920},
  doi =		{10.4230/LIPIcs.SoCG.2020.34},
  annote =	{Keywords: Delaunay triangulation, geometric spanner, plane spanner, stretch factor, spanning ratio}
}

Keywords: Delaunay triangulation, geometric spanner, plane spanner, stretch factor, spanning ratio
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI