Theory Seminar

Title: Fast Computation of Output-Sensitive Maxima in a Word RAM

Speaker: Peyman Afshani, Aarhus University

Time: Wednesday, December 4 at 14:15 to 15:00

Location: Nygaard 395

Abstract:

We look at the problem of computing the maxima of a set of points in three dimensions and we present
an efficient deterministic output-sensitive algorithm in the Word RAM model. We observe that improving 
our algorithm is most likely difficult since it requires breaking a number of important barriers, even if 
randomization is allowed. 

Throughout the talk, we will also discuss many interesting relevant open problems.

Host: Gerth Stølting Brodal