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

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