Discrete Mathematics & Theoretical Computer Science, Vol 6, No 1 (2003)

Font Size:  Small  Medium  Large

Efficient maxima-finding algorithms for random planar samples

Wei-Mei Chen, Hsien-Kuei Hwang, Tsung-Hsi Tsai


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(√nlog 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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page