2017/01/13 by Jérémy Barbay, Barbay, Jérémy, Javiel Rojas +1
Computer Science · Engineering · #Data Management and Algorithms #Computational Geometry and Mesh Generation #Advanced Numerical Analysis Techniques
paper · pdf · doi:10.48550/arxiv.1701.03693
We study the problem of computing the Maxima of a set of n d-dimensional points. For dimensions 2 and 3, there are algorithms to solve the problem with order-oblivious instance-optimal running time. However, in higher dimensions there is still room for improvements. We present an algorithm sensitive to the structural entropy of the input set, which improves the running time, for large classes of instances, on the best solution for Maxima to date for d ≥ 4.