Fast linear expected-time algorithms for computing maxima and convex hulls

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

zbMATH Keywords

convex hullmaximal pointsmaxima algorithm

Mathematics Subject Classification ID

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