Output-sensitive Convex Hull in R^d

What is the best output-sensitive convex hull algorithm for $n$ points in $\mathbb{R}^d$ ?

Abstract

For a set of $n$ points in $\mathbb{R}^d$ whose convex hull has $f$ faces, determine the optimal output-sensitive running time for constructing the hull.

Background and progress

Chan gave an output-sensitive algorithm with running time $O(n\log f+(nf)^{1-\delta}\log^{O(1)}n)$ , where $\delta=1/(\lfloor d/2\rfloor+1)$ , while the output and comparison requirements give a lower bound of $\Omega(n\log f+f)$ [Chan, 1996]. Closing this gap for general $d$ remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p15.

Reference papers

Output-sensitive results on convex hulls, extreme points, and related problemsTimothy M. ChanDiscrete and Computational Geometry · 1996

Output-sensitive Convex Hull in R^d

Coming soon

Organizer