Chen, Wei-Mei and Hwang, Hsien-Kuei and Tsai, Tsung-Hsi - Efficient maxima-finding algorithms for random planar samples

dmtcs:337 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, Vol. 6 no. 1
Efficient maxima-finding algorithms for random planar samples

Authors: Chen, Wei-Mei and Hwang, Hsien-Kuei and Tsai, Tsung-Hsi

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


Source : oai:HAL:hal-00958994v1
Volume: Vol. 6 no. 1
Published on: January 1, 2003
Submitted on: March 26, 2015
Keywords: maxima,average-case analysis,sequential algorithms,sieve algorithms,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 87 times.
This article's PDF has been downloaded 105 times.