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.SWAT.2016.25
URN: urn:nbn:de:0030-drops-60474
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6047/
Go to the corresponding LIPIcs Volume Portal

Amani, Mahdi ; Biniaz, Ahmad ; Bose, Prosenjit ; De Carufel, Jean-Lou ; Maheshwari, Anil ; Smid, Michiel

A Plane 1.88-Spanner for Points in Convex Position

pdf-format:
LIPIcs-SWAT-2016-25.pdf (0.6 MB)

Abstract

Let S be a set of n points in the plane that is in convex position. For a real number t>1, we say that a point p in S is t-good if for every point q of S, the shortest-path distance between p and q along the boundary of the convex hull of S is at most t times the Euclidean distance between p and q. We prove that any point that is part of (an approximation to) the diameter of S is 1.88-good. Using this, we show how to compute a plane 1.88-spanner of S in O(n) time, assuming that the points of S are given in sorted order along their convex hull. Previously, the best known stretch factor for plane spanners was 1.998 (which, in fact, holds for any point set, i.e., even if it is not in convex position).

BibTeX - Entry

@InProceedings{amani_et_al:LIPIcs:2016:6047,
  author =	{Mahdi Amani and Ahmad Biniaz and Prosenjit Bose and Jean-Lou De Carufel and Anil Maheshwari and Michiel Smid},
  title =	{{A Plane 1.88-Spanner for Points in Convex Position}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6047},
  URN =		{urn:nbn:de:0030-drops-60474},
  doi =		{10.4230/LIPIcs.SWAT.2016.25},
  annote =	{Keywords: points in convex position, plane spanner}
}

Keywords: points in convex position, plane spanner
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

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