Next: Problem 16: Simple Polygonalizations
Previous: Problem 14: Binary Space Partition Size
What is the best output-sensitive convex hull algorithm for n points in \R^d?
Uncertain, pending investigation.
Open.
The lower bound is \Omega( n \log f + f ) for f facets (the output size). The best upper bound to date is O( n \log f + (nf)^{1-\delta} \log^{O(1)} n ) with \delta = 1/( \lfloor d/2 \rfloor + 1) [Cha96], which is optimal for sufficiently small f.
convex hulls
J. O’Rourke, 2 Aug. 2001.
Timothy M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Comput. Geom., 16:369–387, 1996.
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. Appl., 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120.