Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem – University of Copenhagen

Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem

Talk by Amr Elmasry

Abstract:
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 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.

About the speaker: Amr Elmasry is affiliated with The Department of Computer Engineering and Systems, Alexandria University, Egypt.

His paper, "Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem", co-authored by Omar Darwish, was accepted at the ESA conference 2014.