2015/10/24 by Darwish, Omar, Elmasry, Amr, Katajainen, Jyrki
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1510.07185
We consider space-bounded computations on a random-access machine (RAM) where the input is given on a read-only random-access medium, the output is to be produced to a write-only sequential-access medium, and the available workspace allows random reads and writes but is of limited capacity. The length of the input is N elements, the length of the output is limited by the computation, and the capacity of the workspace is O(S) bits for some predetermined parameter S. We present a state-of-the-art priority queue---called an adjustable navigation pile---for this restricted RAM model. Under some reasonable assumptions, our priority queue supports minimum and insert in O(1) worst-case time and extract in O(N/S + \lg S) worst-case time for any S ≥ \lg N. We show how to use this data structure to sort N elements and to compute the convex hull of N points in the two-dimensional Euclidean space in O(N2/S + N \lg S) worst-case time for any S ≥ \lg N. Following a known lower bound for the space-time product of any branching program for finding unique elements, both our sorting and convex-hull algorithms are optimal. The adjustable navigation pile has turned out to be useful when designing other space-efficient algorithms, and we expect that it will find its way to yet other applications.