Next: Problem 16: Simple Polygonalizations
Up: The Open Problems Project
Previous: Problem 14: Binary Space
Problem 15: Outputsensitive Convex Hull in
^{d}
 Statement
 What is the best outputsensitive convex hull algorithm
for n points in
^{d}?
 Origin
 Uncertain, pending investigation.
 Status/Conjectures
 Open.
 Partial and Related Results
 The lower bound is
Ω(n log f + f ) for f facets
(the output size).
The best upper bound
to date is
O(n log f + (nf )^{1δ}log^{O(1)}n)
with
δ = 1/(⌊d /2⌋ + 1) [Cha96],
which is optimal for sufficiently small f.
 Appearances
 [MO01]
 Categories
 convex hulls
 Entry Revision History
 J. O'Rourke, 2 Aug. 2001.
 Cha96

Timothy M. Chan.
Outputsensitive results on convex hulls, extreme points, and related
problems.
Discrete Comput. Geom., 16:369387, 1996.
 MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573582, 2001.
Also in SIGACT News 32(3):6372 (2001), Issue 120.
The Open Problems Project  September 19, 2017