On the average number of maximal in a set of vectors

DOI10.1016/0020-0190(89)90156-7zbMath0682.68041OpenAlexW1968246336MaRDI QIDQ1824385

Christian Buchta

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90156-7

zbMATH Keywords

probabilistic analysis of algorithmsrandom pointsgeometric probabilityaverage number of maximamaxima of a set of vectors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (18)

A provably fast linear-expected-time maxima-finding algorithm ⋮ How many maxima can there be? ⋮ Records, the maximal layer, and uniform distributions in monotone sets ⋮ The restrictiveness of the hazard rate order and the moments of the maximal coordinate of a random vector uniformly distributed on the probability \(n\)-simplex ⋮ On random cartesian trees ⋮ Towards estimating expected sizes of probabilistic skylines ⋮ K-dominance in multidimensional data: theory and applications ⋮ Unnamed Item ⋮ Effective space usage estimation for sliding-window skybands ⋮ Exact asymptotics of divide-and-conquer recurrences ⋮ Mellin transforms and asymptotics: Finite differences and Rice's integrals ⋮ Bounding the expected number of rectilinear full Steiner trees ⋮ Dominant skyline query processing over multiple time series ⋮ On some combinatorial identities and harmonic sums ⋮ Sampling-based approximate skyline calculation on big data ⋮ K-Dominance in Multidimensional Data: Theory and Applications ⋮ On the variance of the number of maxima in random vectors and its applications ⋮ Analytic variations on quadtrees

Cites Work

• Unnamed Item
• A note on finding convex hulls via maximal vectors
• Divide and conquer for linear expected time
• On the Average Number of Maxima in a Set of Vectors and Applications

This page was built for publication: On the average number of maximal in a set of vectors