A1359
Title: Computing halfspace depth in $O(n^{d-1})$ via topological sweep
Authors: Rainer Dyckerhoff - University of Cologne (Germany) [presenting]
Erik Mendros - Charles University (Czech Republic)
Stanislav Nagy - Charles University (Czechia)
Abstract: An algorithm for computing the exact halfspace depth of a single point in $\mathbb{R}^d$, $d\ge 3$ is presented. The algorithm achieves asymptotic running time $O(n^{d-1})$, improving upon the previously best known bound $O(n^{d-1}\log n)$. It has two main components. For $d=3$, gnomonic projection is employed to map the data to a plane, point-line duality is applied, and the induced line arrangement is traversed by a topological sweep. For $d>3$, the problem is reduced to the three-dimensional case by means of a suitable projection scheme. The geometric ideas underlying the topological sweep, the use of duality, and the efficient traversal of the arrangement without explicit full construction are highlighted.
