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-δ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.

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.