Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Aronov, Boris; Korman, Matias; Pratt, Simon; van Renssen, André; Roeloffzen, Marcel http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-60522
URL:

; ; ; ;

Time-Space Trade-offs for Triangulating a Simple Polygon

pdf-format:


Abstract

An s-workspace algorithm is an algorithm that has read-only access to the values of the input, write-only access to the output, and only uses O(s) additional words of space. We give a randomized s-workspace algorithm for triangulating a simple polygon P of n vertices, for any s up to n. The algorithm runs in O(n^2/s+n(log s)log^5(n/s)) expected time using O(s) variables, for any s up to n. In particular, the algorithm runs in O(n^2/s) expected time for most values of s.

BibTeX - Entry

@InProceedings{aronov_et_al:LIPIcs:2016:6052,
  author =	{Boris Aronov and Matias Korman and Simon Pratt and André van Renssen and Marcel Roeloffzen},
  title =	{{Time-Space Trade-offs for Triangulating a Simple Polygon}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{30:1--30:12},
  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/6052},
  URN =		{urn:nbn:de:0030-drops-60522},
  doi =		{10.4230/LIPIcs.SWAT.2016.30},
  annote =	{Keywords: simple polygon, triangulation, shortest path, time-space trade-off}
}

Keywords: simple polygon, triangulation, shortest path, time-space trade-off
Seminar: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint Published by LZI