Optimal Convex Hulls for Low-Rank Data in High-Dimensional Space

A 35-year-old algorithmic lemma turns out to be conditional independence on a DAG. Here is what that buys you — and what it doesn’t.

The 10-slide deck that accompanies this preprint walks through the contribution at three levels: what is universal and holds for any data, what is scoped to the rank-r regime, and what is conjectural. Below is the deck as a sequence, with prose between the slides expanding on what each one shows. The full paper, code, and reproducibility notebook are on Zenodo at the end.

CT-QuickHull: optimal convex hulls for low-rank data

For data with intrinsic rank r much less than the ambient dimension d, CT-QuickHull computes the exact convex hull in O(nrd) operations — matching the unconditional lower bound Ω(nrd). That is optimal in this regime.

For full-rank or adversarial high-dimensional data, the algorithm matches the asymptotic complexity of existing methods rather than improving over them. The structural contribution — recognizing the Heritage Lemma as d-separation on an event DAG — is universal and independent of data rank.

Section 9.1 of the paper is explicit about what is and isn’t claimed. The deck and this essay carry the same scope-honest framing throughout.