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

dmtcs:337 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, Vol. 6 no. 1 - https://doi.org/10.46298/dmtcs.337
Efficient maxima-finding algorithms for random planar samplesArticle

Authors: Wei-Mei Chen 1; Hsien-Kuei Hwang 2; Tsung-Hsi Tsai 2

  • 1 Department of Applied Mathematics [Tapei/Tatung]
  • 2 Institute of Statistical Science

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.


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

3 Documents citing this article

Consultation statistics

This page has been seen 270 times.
This article's PDF has been downloaded 380 times.