# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1510.07185.pdf

(Preprint), 577KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Darwish, O., Elmasry, A., & Katajainen, J. (2015). Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls. Retrieved from http://arxiv.org/abs/1510.07185.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0029-5F2C-8

##### 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 $\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.