A volume first maxima-finding algorithm
The maxima-finding is a fundamental problem in computational geometry with many applications. In this paper, a volume first maxima-finding algorithm is proposed. It is proved that the expected running time of the algorithm is N + o(N) when choosing points from CI distribution, which is a new theoretical result when the points belong to d(>2) dimensional space. Experimental results and theoretical analysis indicate that the algorithm runs faster than the Move-To-Front maxima-finding algorithm. (C) 2011 Elsevier B.V. All rights reserved.
computational geometry maxima skyline point probabilistic analysis