zbMATH — the first resource for mathematics

Three-dimensional layers of maxima. (English) Zbl 1090.68114
Summary: We present an \(O(n\log n)\)-time algorithm to solve the three-dimensional layers-of-maxima problem. This is an improvement over the prior \(O(n\log n\log\log n)\)-time solution. A previously claimed \(O(n\log n)\)-time solution due to M. J. Atallah, M. T. Goodrich and K. Ramaiyer [“Biased finger trees and three-dimensional layers of maxima”, in: Proc. 10th ACM symp. on computational geometry, 150–159 (1994)] has technical flaws. Our algorithm is based on a common framework underlying previous work, but to implement it we devise a new data structure to solve a special case of dynamic planar point location in a staircase subdivision. Our data structure itself relies on a new extension to dynamic fractional cascading that allows vertices of high degree in the control graph.

68W05 Nonnumerical algorithms
68P05 Data structures
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI