ausblenden:
Schlagwörter:
Computer Science, Data Structures and Algorithms, cs.DS
Zusammenfassung:
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 $\mathit{minimum}$ and
$\mathit{insert}$ in $O(1)$ worst-case time and $\mathit{extract}$ in $O(N/S +
\lg{} S)$ worst-case time for any $S \geq \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(N^2/S + N \lg{} S)$
worst-case time for any $S \geq \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.
