Fast linear expected-time algorithms for computing maxima and convex hulls
type: Item
instance of: scholarly article
title: Fast linear expected-time algorithms for computing maxima and convex hulls
zbMATH Open document ID: 0766.68132
DOI: 10.1007/BF01188711
author: Kenneth L. Clarkson
author: David B. Levine
author: Jon Bentley
published in: Algorithmica
publication date: 1993-04-01T00:00:00Z
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 148917
zbMATH Keywords: maximal points
zbMATH Keywords: maxima algorithm
zbMATH Keywords: convex hull
MaRDI profile type: Publication
cites work: Multidimensional divide-and-conquer
cites work: Divide and conquer for linear expected time
cites work: On the Average Number of Maxima in a Set of Vectors and Applications
cites work: Optimal Expected-Time Algorithms for Closest Point Problems
cites work: Applications of random sampling in computational geometry. II
cites work: A note on finding convex hulls via maximal vectors
cites work: Expected time bounds for selection
cites work: An efficient algorithm for determining the convex hull of a finite planar set
cites work: On Finding the Maxima of a Set of Vectors
cites work: Combinatorial solutions of multidimensional divide-and-conquer recurrences
cites work: Convex hulls of finite sets of points in two and three dimensions
cites work: Q3694703
full work available at URL: https://doi.org/10.1007/bf01188711
OpenAlex ID: W3136083256
Recommended article: A provably fast linear-expected-time maxima-finding algorithm
Recommended article: Q3974960
Recommended article: LATIN 2004: Theoretical Informatics
Recommended article: Linear time algorithms for convex and monotone approximation
Recommended article: A fast approximation to a convex hull
Recommended article: Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima.
Recommended article: Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
Recommended article: Q3716334
Recommended article: Optimal computation of finitely oriented convex hulls
description: scientific article; zbMATH DE number 148917