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 samples

Authors: 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(√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]

    1 Document citing this article

    Share

    Consultation statistics

    This page has been seen 207 times.
    This article's PDF has been downloaded 318 times.