  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.
