Chen, Wei-Mei; Hwang, Hsien-Kuei; Tsai, Tsung-Hsi Efficient maxima-finding algorithms for random planar samples. (English) Zbl 1036.68124 Discrete Math. Theor. Comput. Sci. 6, No. 1, 107-122 (2003). Summary: We collect major known algorithms in the literature for finding the maxima of multi-dimensional points and provide a simple classification. Several new algorithms are proposed. In particular, we give a new maxima-finding algorithm with expected complexity \(n+O (\sqrt {n\log n}) \) when the input is a sequence of points uniformly chosen at random from general planar regions. We also give a sequential algorithm, very efficient for practical purposes. Cited in 1 ReviewCited in 9 Documents MSC: 68W05 Nonnumerical algorithms Keywords:maxima; average-case analysis; sequential algorithms; sieve algorithms PDFBibTeX XMLCite \textit{W.-M. Chen} et al., Discrete Math. Theor. Comput. Sci. 6, No. 1, 107--122 (2003; Zbl 1036.68124) Full Text: EuDML EMIS