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(kn^{ 2 - { 1 \over \log{ k}} + \log_k{ \left(1 + { 2 \over { 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(kn^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.
Categories: cs.CG cs.DS