2010/07/09 by Yakov Nekrich, Nekrich, Yakov
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1007.1593
openalex publication_date 2010/07/09 · arxiv created 2011/05/03 · arxiv updated 2011/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the three-dimensional layers-of-maxima problem can be solved in o(nlog n) time in the word RAM model. Our algorithm runs in O(n(log log n)3) deterministic time or O(n(loglog n)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(nlog n) time in the pointer machine model.