We revisit the read-only random-access model, in which the input array is read-only and a limited amount of workspace is allowed. Given a set of N two-dimensional points in a read-only input array and direct-(S) bits of extra workspace (where S ≥ lg N), we present an algorithm that runs in O(N~2/S + N lg S) time for constructing the convex hull formed by the given points. Following a lower bound for sorting, our algorithm is asymptotically optimal with respect to the read-only random-access model. Of independent interest, we introduce a space-efficient data structure that we call the augmented memory-adjustable navigation pile. We expect this data structure to be a useful tool when designing other space-efficient algorithms.
展开▼
机译：我们重新审视了只读随机访问模型，在该模型中，输入数组是只读的，并且只允许有限的工作空间。给定一个只读输入数组中的N个二维点集和额外工作空间的直接（S）位（其中S≥lg N），我们提出一种算法，该算法在O（N〜2 / S + N lg S）构造由给定点形成的凸包的时间。遵循排序的下限，相对于只读随机访问模型，我们的算法是渐近最优的。出于个人利益，我们介绍了一种节省空间的数据结构，我们称其为增强型内存可调导航桩。我们希望这种数据结构在设计其他节省空间的算法时将是一个有用的工具。
展开▼
