next up previous
Next: Problem 16: Simple Polygonalizations Up: The Open Problems Project Previous: Problem 14: Binary Space


Problem 15: Output-sensitive Convex Hull in $ \mathbb {R}$d

Statement
What is the best output-sensitive convex hull algorithm for n points in $ \mathbb {R}$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-δlogO(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.

Bibliography

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.



The Open Problems Project - December 04, 2015