| Memory-adjustable navigation piles with applications to sorting and convex hulls | |
| Authors: | Omar Darwish, Amr Elmasry, and Jyrki Katajainen |
| Publication: | E-print arXiv:1510.07185, arXiv.org (2015), 21 pp. |
| Full text: |  HTML |
| Abstract: | 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 use lg x as a shorthand for log2(max{2, x}).) 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. |
| Related: | HTML (Conference paper) |
| BibLATEX: | @report{DEK2015R,
author = {Omar Darwish and Amr Elmasry and Jyrki Katajainen},
title = {Memory-adjustable navigation piles with applications to sorting and
convex hulls},
type = {E-print},
number = {arXiv:1510.07185},
institution = {arXiv.org},
year = {2015},
pagetotal = {21},
}
|