Fast linear expected-time algorithms for computing maxima and convex hulls
From MaRDI portal
Publication:1206440
DOI10.1007/BF01188711zbMath0766.68132OpenAlexW3136083256MaRDI QIDQ1206440
David B. Levine, Kenneth L. Clarkson, Jon Louis Bentley
Publication date: 1 April 1993
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01188711
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
In-place algorithms for computing (Layers of) maxima ⋮ Computing efficiently the nondominated subset of a set sum ⋮ Simple and efficient bi-objective search algorithms via fast dominance checks ⋮ Maxima-finding algorithms for multidimensional samples: A two-phase approach ⋮ Convex-hull algorithms: implementation, testing, and experimentation ⋮ Sampling-based approximate skyline calculation on big data ⋮ On the variance of the number of maxima in random vectors and its applications
Cites Work
- Unnamed Item
- Multidimensional divide-and-conquer
- A note on finding convex hulls via maximal vectors
- Divide and conquer for linear expected time
- Applications of random sampling in computational geometry. II
- An efficient algorithm for determining the convex hull of a finite planar set
- Combinatorial solutions of multidimensional divide-and-conquer recurrences
- Optimal Expected-Time Algorithms for Closest Point Problems
- Expected time bounds for selection
- On Finding the Maxima of a Set of Vectors
- Convex hulls of finite sets of points in two and three dimensions
- On the Average Number of Maxima in a Set of Vectors and Applications