A Lower Bound to Finding Convex Hulls
From MaRDI portal
Publication:3922189
DOI10.1145/322276.322289zbMath0468.68080OpenAlexW2094855951WikidataQ60358420 ScholiaQ60358420MaRDI QIDQ3922189
Publication date: 1981
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322276.322289
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items
Distribution-sensitive algorithms ⋮ A variant of Ben-Or's lower bound for algebraic decision trees ⋮ Finding the convex hull of a sorted point set in parallel ⋮ On selecting the k largest with median tests ⋮ Optimal parallel algorithms for computing convex hulls and for sorting ⋮ A lower bound for randomized algebraic decision trees ⋮ Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination ⋮ An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons ⋮ Comments on a lower bound for convex hull determination ⋮ Routing in a polygonal terrain with the shortest beacon watchtower ⋮ How to reduce the average complexity of convex hull finding algorithms ⋮ Efficiently testing digital convexity and recognizing digital convex polygons ⋮ Linear decision trees are too weak for convex hull problem ⋮ On the complexity of finding the convex hull of a set of points ⋮ Maintenance of configurations in the plane ⋮ A new algorithm for computing the convex hull of a planar point set ⋮ On the complexity of the extreme points decision problem ⋮ Randomized quickhull ⋮ Fast randomized parallel methods for planar convex hull construction ⋮ Quasi-Monotonic Sequences: Theory, Algorithms and Applications ⋮ A note on bicriterion programming ⋮ Convex hull properties and algorithms ⋮ On computing approximate convex hulls ⋮ A filtering technique for fast convex hull construction in \(\mathbb{R}^2\) ⋮ Constructing the convex hull of a partially sorted set of points ⋮ Lower bounds for maximal and convex layers problems ⋮ Efficient Algorithms to Test Digital Convexity ⋮ An optimal algorithm to compute the inverse beacon attraction region ⋮ Some performance tests of convex hull algorithms ⋮ Finding the Convex Hull of Discs in Parallel ⋮ Some dynamic computational geometry problems
