**Next:** Problem 16: Simple Polygonalizations

**Previous:** Problem 14: Binary Space Partition Size

- Statement
What is the best output-sensitive convex hull algorithm for n points in \R^d?

- Origin
Uncertain, pending investigation.

- Status/Conjectures
Open.

- Partial and Related Results
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.

- Appearances
- Categories
convex hulls

- Entry Revision History
J. O’Rourke, 2 Aug. 2001.

- [Cha96]
Timothy M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems.

*Discrete Comput. Geom.*, 16:369–387, 1996.- [MO01]
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.