# zbMATH — the first resource for mathematics

Improved linear expected-time algorithms for computing maxima. (English) Zbl 1196.68298
Farach-Colton, Martin (ed.), LATIN 2004: Theoretical informatics. 6th Latin American symposium, Buenos Aires, Argentina, April 5–8, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21258-2/pbk). Lecture Notes in Computer Science 2976, 181-192 (2004).
Summary: The problem of finding the maxima of a point set plays a fundamental role in computational geometry. Based on the idea of the certificates of exclusion, two algorithms are presented to solve the maxima problem under the assumption that $$N$$ points are chosen from a $$d$$-dimensional hypercube uniformly and each component of a point is independent of all other components. The first algorithm runs in $$O(N)$$ expected time and finds the maxima using $$dN+ d\ln N+d^2N^{1-1/d}(\ln N)^{1/d}+O(dN^{1-1/d})$$ expected scalar comparisons. The experiments show the second algorithm has a better expected running time than the first algorithm while a tight upper bound of the expected running time is not obtained. A third maxima-finding algorithm is presented for $$N$$ points with a $$d$$-dimensional component independence distribution, which runs in $$O(N)$$ expected time and uses $$2dN+O(\ln N(\ln(\ln N)))+d^2N^{1-1/d}(\ln N)^{1/d}+O(dN^{1-1/d})$$ expected scalar comparisons. The substantial reduction of the expected running time of all three algorithms, compared with some known linear expected-time algorithms, has been attributed to the fact that a better certificate of exclusion has been chosen and more non-maximal points have been identified and discarded.
For the entire collection see [Zbl 1048.68003].

##### MSC:
 68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: