Computing Maximal Layers Of Points in $E^{f(n)}$

Abstract

In this paper we present a randomized algorithm for computing the collection of maximal layers for a point set in $E^k$ ($k=f(n)$). The input to our algorithm is a point set $P=\{p_1,...,p_n\}$ with $p_i\in E^k$. The proposed algorithm achieves a runtime of $O\left(k{n}^{2-\frac{1}{\log k}+{\log }_k\left(1+\frac{2}{k+1}\right)}\log n\right)$ when $P$ is a random order and a runtime of $O(k^2{n}^{3/2+({\log }_k(k-1))/2}\log n)$ for an arbitrary $P$. Both bounds hold in expectation. Additionally, the run time is bounded by $O(k{n}^2)$ in the worst case. This is the first non-trivial algorithm whose run-time remains polynomial whenever $f(n)$ is bounded by some polynomial in $n$ while remaining sub-quadratic in $n$ for constant $k$. The algorithm is implemented using a new data-structure for storing and answering dominance queries over the set of incomparable points.

13 pages, submitted to LATIN 2016