In this paper we present a randomized algorithm for solving the maximal layers problem for a random order. That is, given a point set $P = \{p_1,...,p_n\}$ with $p_i \in [0,1]^k$ picked uniformly at random, compute the successive maximal layers of $P$. The algorithm achieves a runtime of $o(n^2)$ in expectation. Additionally, the algorithm has a runtime of $o(kn^2)$ when $k$ is not a constant. To the best of our knowledge this is the first such algorithm for the problem (for non-constant $k$). The algorithm is implemented using a new data-structure for storing and answering dominance queries over the set of incomparable points.
['Indranil Banerjee', 'Dana Richards']
On Maximal Layers Of Random Orders