# 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.

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