Date: 06 Sep 2014
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)


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: