License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.281
URN: urn:nbn:de:0030-drops-39411
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3941/
Go to the corresponding LIPIcs Volume Portal

Barba, Luis ; Korman, Matias ; Langerman, Stefan ; Silveira, Rodrigo I. ; Sadakane, Kunihiko

Space-Time Trade-offs for Stack-Based Algorithms

pdf-format:
29.pdf (0.7 MB)

Abstract

In memory-constrained algorithms we have read-only access to the input, and the number of additional variables is limited. In this paper we introduce the compressed stack technique, a method that allows to transform algorithms whose space bottleneck is a stack into memory-constrained algorithms. Given an algorithm A that runs in O(n) time using a stack of length Theta(n), we can modify it so that it runs in O(n^2/2^s) time using a workspace of O(s) variables (for any s \in o(log n)) or O(n log n/log p)$ time using O(p log n/log p) variables (for any 2 <= p <= n). We also show how the technique can be applied to solve various geometric problems, namely computing the convex hull of a simple polygon, a triangulation of a monotone polygon, the shortest path between two points inside a monotone polygon, 1-dimensional pyramid approximation of a 1-dimensional vector, and the visibility profile of a point inside a simple polygon. Our approach exceeds or matches the best-known results for these problems in constant-workspace models (when they exist), and gives a trade-off between the size of the workspace and running time. To the best of our knowledge, this is the first general framework for obtaining memory-constrained algorithms.

BibTeX - Entry

@InProceedings{barba_et_al:LIPIcs:2013:3941,
  author =	{Luis Barba and Matias Korman and Stefan  Langerman and Rodrigo I. Silveira and Kunihiko Sadakane},
  title =	{{Space-Time Trade-offs for Stack-Based Algorithms}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{281--292},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3941},
  URN =		{urn:nbn:de:0030-drops-39411},
  doi =		{10.4230/LIPIcs.STACS.2013.281},
  annote =	{Keywords: space-time trade-off, constant workspace, stack algorithms}
}

Keywords: space-time trade-off, constant workspace, stack algorithms
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

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