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.
Recommended Citation
A. Banerjee and D. Richards, "Computing Maximal Layers of Points in Eᶠ⁽ⁿ⁾," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9644, pp. 138 - 151, Springer Verlag, Apr 2016.
The definitive version is available at https://doi.org/10.1007/978-3-662-49529-2_11
Meeting Name
12th Latin American Symposium on Theoretical Informatics, LATIN 2016 (2016: Apr. 11-15, Ensenada, Mexico)
Department(s)
Computer Science
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
Comments
Published as Indranil Banerjee.