← All problems

Output-sensitive Convex Hull in R^d

Let dd be fixed, let SS be a set of nn points in Rd\mathbb{R}^d, and let the boundary complex of conv(S)\operatorname{conv}(S) have ff faces. Determine whether the convex hull can be constructed in O(nlogf+f)O(n\log f+f) time, or otherwise determine the tight worst-case output-sensitive complexity as a function of nn, ff, and dd.

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li