  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 \alg\ that runs in O(n) time using $\Theta(n)$ variables, we can
modify it so that it runs in $O(n^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\leq p\leq 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
the first 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.
