Divide and conquer for linear expected time

DOI10.1016/0020-0190(78)90051-0zbMath0404.68046OpenAlexW2020085260MaRDI QIDQ1256853

Jon Louis Bentley, Michael Ian Shamos

Publication date: 1978

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

Full work available at URL: https://doi.org/10.1016/0020-0190(78)90051-0

zbMATH Keywords

Linear ProgrammingComputational GeometryAverage-Case AlgorithmsConvex NullDesigning Fast AlgorithmsDivide-And-Conquer TechniqueWorst-Case Time Complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Algorithms in computer science (68W99)

Related Items

Quasi-convex optimization, Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points, Records, the maximal layer, and uniform distributions in monotone sets, Linear programming approaches to the convex hull problem in \(\mathbb{R}^ m\), On determining the on-line minimax linear fit to a discrete point set in the plane, Some problems in computational geometry, Fast algorithms for computing the diameter of a finite planar set, On random cartesian trees, An O(n) algorithm for discrete n-point convex approximation with applications to continuous case, Another efficient algorithm for convex hulls in two dimensions, Voronoi diagrams from convex hulls, The relative neighbourhood graph of a finite planar set, A note on linear expected time algorithms for finding convex hulls, A note on finding convex hulls via maximal vectors, Further comments on Bykat's convex hull algorithm, How to reduce the average complexity of convex hull finding algorithms, On the computer generation of random convex hulls, Maintenance of configurations in the plane, An efficient and numerically correct algorithm for the 2D convex hull problem, Moment inequalities for random variables in computational geometry, Convex hulls of samples from spherically symmetric distributions, Comments on convex hull of a finite set of points in two dimensions, Randomized quickhull, Comments on convex hull of a finite set of points in two dimensions, Fast linear expected-time algorithms for computing maxima and convex hulls, Quasi-Monotonic Sequences: Theory, Algorithms and Applications, The average performance analysis of a closest‐pair algorithm, O(n) algorithms for discrete n-point approximation by quasi-convex functions, A simple algorithm for building the 3-D convex hull, DATA GENERATION FOR GEOMETRIC ALGORITHMS ON NON-UNIFORM DISTRIBUTIONS, On computing approximate convex hulls, Convex Hulls of Random Walks, Optimal speeding up of parallel algorithms based upon the divide-and- conquer strategy, The plane with parallel coordinates, On the average number of maximal in a set of vectors, On the variance of the number of maxima in random vectors and its applications, Linear time algorithms for convex and monotone approximation, A note on the expected time required to construct the outer layer, Globally determining a minimum-area rectangle enclosing the projection of a higher-dimensional set, Lipschitz condition in minimum norm problems on bounded functions, Exact balancing is not always good

Uses Software

• Quicksort

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An efficient algorithm for determining the convex hull of a finite planar set
• On the identification of the convex hull of a finite set of points in the plane
• Convex hulls of finite sets of points in two and three dimensions
• A New Convex Hull Algorithm for Planar Sets
• [https://portal.mardi4nfdi.de/wiki/Publication:5331598 �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten. II]
• The convex hull of a random set of points
• ZufÄllige konvexe Polygone in einem Ringgebiet
• Sur L'enveloppe convexe des nuages de points aleatoires dans Rⁿ. I
• [https://portal.mardi4nfdi.de/wiki/Publication:5588965 Die konvexe H�lle von n rotationssymmetrisch verteilten Punkten]