Title: Constructing Shallow Cuttings Efficiently

Speaker: Konstantinos Tsakalidis, Chinese University of Hong Kong

Time/Date: Friday, Apr 11, 11-12
Location: Room 3501

Abstract:

Shallow cuttings are fundamental tools in range searching as many
problems admit efficient static data structures and offline
algorithms due to their application. In this talk I will present our
recent results on shallow cuttings for ``3D dominance ranges'' and their
implications to ``orthogonal range searching''.

First I will present deterministic algorithms that ``construct'' single
and multiple optimal-sized shallow cuttings using optimal time and
space in the comparison model [SODA14]. Previously only polynomial
worst-case time could be achieved and in fact our algorithms yield
worst-case efficient and optimal preprocessing time for a series of
important orthogonal range searching problems in the pointer machine
and the word-RAM models.

In the second part I will show the intricate way in which an
improved version of our construction algorithm yields the first
worst-case efficient algorithm for the ``rectangle enclosure'' problem
in the word-RAM model [ICALP14], which in turn implies the currently
most efficient algorithm for the general ``offline dominance range
reporting'' problem.

Joint work with Peyman Afshani (MADALGO) and Timothy Chan (UWaterloo).

[SODA14] Peyman Afshani, Konstantinos Tsakalidis: Optimal
Deterministic Shallow Cuttings for 3D Dominance Ranges. SODA 2014:
1389-1398

[ICALP14] Peyman Afshani, Timothy Chan, Konstantinos Tsakalidis:
Deterministic Rectangle Enclosure and Offline Dominance Reporting on
the RAM. Submitted to ICALP 2014