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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, 6 (1), pp.107-122
Liste complète des métadonnées

Littérature citée [64 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958994
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:59:38
Dernière modification le : mercredi 24 janvier 2018 - 10:46:02
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:12:51

Fichier

dm060109.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

113

Téléchargements de fichiers

488