Date: 06 Sep 2014 From: jyrki@di.ku.dk Subject: 11/9–19/9: Amr will be at our department Guest talk: Optimal time-space tradeoff for the 2d convex-hull problem Speaker: Amr Elmasry, Alexandria University Time: Monday, 15 September 2014 at 14.00–15.00 Place: APL meeting room (Universitetsparken 5) 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. (joint work with Omar Darwish) PE-lab's home page: http://www.diku.dk/~jyrki/PE-lab/