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, (2015), 21 pp.
Full text:<html.gif>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.gif>HTML (Conference paper)  
  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 = {},
  year = {2015},
  pagetotal = {21},
This page was generated by Jyrki Katajainen <> on 28.10.2015.