Output-sensitive Convex Hull in $\mathbb{R}^d$

Definitions and mathematical statement

Fix a dimension $d\ge4$. Given $n$ points $S\subset\mathbb R^d$, compute the boundary facets of $P=\operatorname{conv}(S)$. In the general-position case, $P$ is full-dimensional and every facet has $d$ vertices, so the output consists of $f$ constant-size facet descriptions. The dimension is fixed independently of $n$.

An output-sensitive algorithm has a running time bounded in terms of both $n$ and the actual number $f$ of facets, rather than the largest possible hull size for $n$ points. Determine the optimal such bound. The natural sharp target in the geometric comparison model is \[ O(n\log(f+1)+f). \] An algorithm should produce the facets and their supporting data, and its accounting must include all work spent on intermediate faces or intermediate hulls. A small final output does not justify ignoring a large intermediate enumeration.

For degenerate inputs, a non-simplicial facet can have many vertices; then output size should include the chosen incidence representation. The displayed formulation isolates the general-position core of the source question. Arithmetic operations and orientation tests on fixed-size coordinate tuples have unit cost; coordinate bit complexity is a separate model choice.

Short English statement

Can a high-dimensional convex hull be computed in time governed by the input and its actual facet output, matching the natural $n\log f+f$ target?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500015 (AMR-054-0015), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 15. Original source indexed by AMR-054-0015. https://topp.openproblem.net/p15.