TITLE: An Improved Algorithm for Static 3D Dominance Reporting in the Pointer Machine

Speaker: Konstaninos Tsakalidis, HKUST


Abstract:

We present an efficient algorithm for the pointer machine model that
preprocesses a set of~$n$ three-dimensional points in $O(n\log n)$
worst case time to construct an $O(n)$ space data structure that
supports three-dimensional dominance reporting queries in $O(\log
n+ t)$ worst case time, when $t$ points are reported.
Previous results achieved either $O(n^2)$ worst case or $O(n\log n)$
expected preprocessing time. We achieve efficient worst case time by
using partially persistent data structures.