1 Search Results for "Amani, Mahdi"


Document
A Plane 1.88-Spanner for Points in Convex Position

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

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)


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).

Cite as

Mahdi Amani, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, and Michiel Smid. A Plane 1.88-Spanner for Points in Convex Position. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{amani_et_al:LIPIcs.SWAT.2016.25,
  author =	{Amani, Mahdi and Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Maheshwari, Anil and Smid, Michiel},
  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 =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.25},
  URN =		{urn:nbn:de:0030-drops-60474},
  doi =		{10.4230/LIPIcs.SWAT.2016.25},
  annote =	{Keywords: points in convex position, plane spanner}
}
  • Refine by Author
  • 1 Amani, Mahdi
  • 1 Biniaz, Ahmad
  • 1 Bose, Prosenjit
  • 1 De Carufel, Jean-Lou
  • 1 Maheshwari, Anil
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 plane spanner
  • 1 points in convex position

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail