Title

Computing Maximal Layers of Points in Eᶠ⁽ⁿ⁾

Abstract

In this paper we present a randomized algorithm for computing the collection of maximal layers for a point set in Ek (k = f(n)). The input to our algorithm is a point set P = {p1,..., pn} with pi ∈ Ek. The proposed algorithm achieves a runtime of O (formula presented) when P is a random order and a runtime of O(formula presented) for an arbitrary P. Both bounds hold in expectation. Additionally, the run time is bounded by O(knk) 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 (in expectation). The algorithm is implemented using a new data-structure for storing and answering dominance queries over the set of incomparable points.

Meeting Name

12th Latin American Symposium on Theoretical Informatics, LATIN 2016 (2016: Apr. 11-15, Ensenada, Mexico)

Department(s)

Computer Science

Comments

Published as Indranil Banerjee.

Keywords and Phrases

Complexity; Maximal Layers; Random Order

International Standard Book Number (ISBN)

978-366249528-5

International Standard Serial Number (ISSN)

0302-9743

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2016 Springer Verlag, All rights reserved.

Publication Date

15 Apr 2016

Share

 
COinS