Skip to Main content Skip to Navigation
Journal articles

Efficient maxima-finding algorithms for random planar samples

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [64 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958994
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:59:38 PM
Last modification on : Wednesday, January 24, 2018 - 10:46:02 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:12:51 PM

File

dm060109.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00958994, version 1

Collections

Citation

Wei-Mei Chen, Hsien-Kuei Hwang, Tsung-Hsi Tsai. Efficient maxima-finding algorithms for random planar samples. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, 6 (1), pp.107-122. ⟨hal-00958994⟩

Share

Metrics

Record views

186

Files downloads

1363