Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons

Abstract

Constant-work-space algorithms model computation when space is at a premium: the input is given as a read-only array that allows random access to its entries, and the algorithm may use constantly many additional registers of O(logn) bits each, where n denotes the input size. We present such algorithms for two restricted variants of the shortest path problem. First, we describe how to report a simple path between two arbitrary nodes in a given tree. Using a technique called "computing instead of storing", we obtain a naive algorithm that needs quadratic time and a constant number of additional registers. We then show how to improve the running time to linear by applying a technique named "simulated parallelization". Second, we show how to compute a shortest geodesic path between two points in a simple polygon in quadratic time and with constant work-space.