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} i n E^{k}

. The proposed algorithm achieves a runtime of

O l e f t (k n^{2 - 1 o v e r l o g k + l o g_{k} l e f t (1 + 2 o v e r k + 1 i g h t)} l o g n i g h t)

when

P

is a random order and a runtime of

O (k^{2} n^{3 / 2 + (l o g_{k} (k - 1)) / 2} l o g 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.

Recommendations

Cited in

(4)

This page was built for publication: Computing maximal layers of points in \(E^{f(n)}\)