2026-07-20T05:48:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3941 2024-03-06T10:34:40Z ddc:004 open_access

Space-Time Trade-offs for Stack-Based Algorithms Barba, Luis Korman, Matias Langerman, Stefan Silveira, Rodrigo I. Sadakane, Kunihiko space-time trade-off constant workspace stack algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luis Barba and Matias Korman and Stefan Langerman and Rodrigo I. Silveira and Kunihiko Sadakane 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.281 urn:nbn:de:0030-drops-39411 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.281 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode