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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Space-Time Trade-offs for Stack-Based Algorithms


    Beteiligte:

    Erscheinungsdatum :

    2013-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    004 / 629




    Accuracy vs Efficiency Trade-offs in Optical Flow Algorithms

    Liu, H. / Hong, T.-H. / Herman, M. et al. | British Library Online Contents | 1998


    Propulsion system design trade-offs for space stations

    JONES, JEFFREY / ZIMMERMANN, FRANK / FRANCE, CORY | AIAA | 1993


    Propulsion system design trade-offs for space stations

    Jones, Jeffrey D. / Zimmermann, Frank S. / France, Cory P. | NTRS | 1993


    MMW system trade-offs

    Currie, N.C. / Parker, S.W. / Efurd, R.B. | IEEE | 1988