A Fast Algorithm for Three-Dimensional Layers of Maxima Problem

DOI10.1007/978-3-642-22300-6_51MaRDI QIDQ5199277zbMATH OpenOpenAlexFDO

Authors Yakov Nekrich

Publication date 12 August 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.1593

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms (68W40)

Abstract: We show that the three-dimensional layers-of-maxima problem can be solved in $o(nlogn)$ time in the word RAM model. Our algorithm runs in $O(n(loglogn{)}^3)$ deterministic time or $O(n(loglogn{)}^2)$ expected time and uses O(n) space. We also describe an algorithm that uses optimal O(n) space and solves the three-dimensional layers-of-maxima problem in $O(nlogn)$ time in the pointer machine model.

Recommendations

• In-place algorithms for computing (Layers of) maxima
• In-Place Algorithms for Computing (Layers of) Maxima
• Approximation Algorithms for Max 3-Section Using Complex Semidefinite Programming Relaxation
• Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima.
• A fast adaptive multipole algorithm in three dimensions
• Fast algorithms for the maximum convolution problem
• A provably fast linear-expected-time maxima-finding algorithm
• scientific article; zbMATH DE number 218054
• Extending the Stansfield Algorithm to Three Dimensions: Algorithms and Implementations
• The Simplex Algorithm in Dimension Three

Cited in

(7)

• A stable algorithm for 3D-IHCP
• Three-dimensional layers of maxima
• Algorithms for three-dimensional dominance searching in linear space.
• scientific article; zbMATH DE number 1947398 (Why is no real title available?)
• Fast computation of output-sensitive maxima in a word RAM
• In-Place Algorithms for Computing (Layers of) Maxima
• In-place algorithms for computing (Layers of) maxima

This page was built for publication: A Fast Algorithm for Three-Dimensional Layers of Maxima Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199277)