Extreme points

Definitions and mathematical statement

Fix an integer $d>3$. For a finite set $S=\{p_1,\ldots,p_n\}\subset{\mathbb{R}}^d$, its convex hull is \[ \operatorname{conv}(S)=\left\{\sum_{i=1}^n\lambda_i p_i:\lambda_i\geq0,\ \sum_{i=1}^n\lambda_i=1\right\}. \] A point $p\in S$ is a convex-hull vertex, or extreme point, exactly when $p\notin\operatorname{conv}(S\setminus\{p\})$. Consider the decision problem of determining whether \[ \forall p\in S,\qquad p\notin\operatorname{conv}(S\setminus\{p\}). \] The required output is a yes/no answer that every input point is extreme; it is not the full face structure of the convex hull.

Put $q=\lfloor d/2\rfloor$ and $a_d=2q/(q+1)$. The source asks for an algorithm for this decision problem faster in the worst case than its reported best known "near-$n^{a_d}$" bound, or a matching lower bound. Dimension is fixed, so any constants may depend on $d$. The record does not specify what factors "near" suppresses, which improvement qualifies, the computation model, deterministic versus randomized guarantees, or permitted degeneracies. Consequently an exact $o(n^{a_d})$ target or a model-specific lower-bound assertion cannot be inferred from the wording alone.

Short English statement

In each fixed dimension $d\geq4$, decide whether every point of an input set is a convex-hull vertex. Improve the reported near-$n^{2\lfloor d/2\rfloor/(\lfloor d/2\rfloor+1)}$ running time, or establish a matching lower bound in a specified computation model.

Sources

• Local UnsolvedMath registry, permanent ID 3800013, exact source code catalogue entry, "Extreme points"; proposed by Jeff Erickson and cited proposers. Registry status open, classification OPEN-TRIAGE.
• Jeff Erickson, Open Problems in Computational Geometry, "Extreme points", https://jeffe.cs.illinois.edu/open/. Supplied HTML extraction accessed July 29, 2026. No precise algorithm or lower-bound citation is supplied in this record.
• The supplied research summary labels the problem still open and reports no improved algorithm or matching lower bound. It also mentions $O(n^{\lfloor d/2\rfloor})$ convex-hull computation and near-$n^{a_d}$-type bounds; computing a full hull and deciding whether all points are vertices have different output requirements, so these descriptions are not identified as equivalent tasks.
• The source warns that its pages have not been systematically updated since 2001. The provenance flags status NEEDS_REVIEW; public access was verified but redistribution permission was not established, so rights are also NEEDS_REVIEW. No independent current-status verification is asserted.