A Lower Bound to Finding Convex Hulls
From MaRDI portal
Publication:3922189
DOI10.1145/322276.322289zbMATH Open0468.68080DBLPjournals/jacm/Yao81bOpenAlexW2094855951WikidataQ60358420 ScholiaQ60358420MaRDI QIDQ3922189FDOQ3922189
Authors: Andrew Chi-Chih Yao 
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)
Cited In (33)
- A new algorithm for computing the convex hull of a planar point set
- Subquadratic algorithms for algebraic 3SUM
- Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems
- Finding the Convex Hull of Discs in Parallel
- Comments on a lower bound for convex hull determination
- How to reduce the average complexity of convex hull finding algorithms
- A variant of Ben-Or's lower bound for algebraic decision trees
- Linear decision trees are too weak for convex hull problem
- On selecting the k largest with median tests
- Constructing the convex hull of a partially sorted set of points
- Efficient Algorithms to Test Digital Convexity
- On computing approximate convex hulls
- An optimal algorithm to compute the inverse beacon attraction region
- On the complexity of finding the convex hull of a set of points
- Fast randomized parallel methods for planar convex hull construction
- Efficiently testing digital convexity and recognizing digital convex polygons
- Randomized quickhull
- On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination
- Optimal parallel algorithms for computing convex hulls and for sorting
- Routing in a polygonal terrain with the shortest beacon watchtower
- Maintenance of configurations in the plane
- Some dynamic computational geometry problems
- Quasi-Monotonic Sequences: Theory, Algorithms and Applications
- A filtering technique for fast convex hull construction in \(\mathbb{R}^2\)
- Convex hull properties and algorithms
- Finding the convex hull of a sorted point set in parallel
- On the complexity of the extreme points decision problem
- Distribution-sensitive algorithms
- Some performance tests of convex hull algorithms
- A note on bicriterion programming
- An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
- A lower bound for randomized algebraic decision trees
- Lower bounds for maximal and convex layers problems
This page was built for publication: A Lower Bound to Finding Convex Hulls
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3922189)
