High Incidence Partitions and Minimum Ellipsoid Coresets

Definitions and mathematical statement

Two questions recorded under one permanent ID.

(1) Incidence in convex-cell partitions. The supplied record asks whether, for every incidence threshold $c$, there exists a locally finite partition $\mathcal P$ of ${\mathbb{R}}^3$ into convex cells such that \[ \#\{v\in V(\mathcal P):v\text{ is incident with }C\}\ge c \quad\text{for every }C\in\mathcal P, \] \[ \#\{C\in\mathcal P:v\text{ is incident with }C\}\ge c \quad\text{for every }v\in V(\mathcal P). \] Here $V(\mathcal P)$ denotes the intended set of vertices, and local finiteness means that every compact subset of ${\mathbb{R}}^3$ meets only finitely many cells. For closed cells, the natural interpretation of incidence is $v\in C$. The source record does not specify whether cells must be polyhedral, bounded, full-dimensional, or face-to-face, or whether an incident vertex must be a vertex of the particular cell. These choices affect the meaning of $V(\mathcal P)$ and must be resolved before this becomes a precise existence question. The domain of $c$ is also unspecified; positive integer thresholds give the usual incidence interpretation, but this convention is not explicitly supplied.

(2) Subsets and minimum enclosing ellipsoids. For a finite set $S\subset{\mathbb{R}}^d$, the record denotes its minimum enclosing ellipsoid by $\operatorname{MEE}(S)$ and calls $\operatorname{DBM}$ the Banach--Mazur distance. It proposes \[ f(d,\varepsilon)= \sup_{\substack{S\subset{\mathbb{R}}^d\\S\text{ finite}}} \min\left\{|X|:X\subseteq S,\quad \operatorname{DBM}\left(\operatorname{MEE}(X),\operatorname{MEE}(S)\right) \le\varepsilon\right\}, \] and asks whether \[ f(d,\varepsilon)=O\!\left(\frac{d}{\varepsilon^2}\right). \] This displays the supplied target literally; several ingredients remain unresolved. For a finite set $T$ with $\operatorname{aff}(T)={\mathbb{R}}^d$, the usual minimum-volume enclosing ellipsoid minimizes volume among ellipsoids \[ E(a,A)=\{x\in{\mathbb{R}}^d:(x-a)^{\mathsf T}A^{-1}(x-a)\le1\}, \qquad a\in{\mathbb{R}}^d,\quad A=A^{\mathsf T}\succ0, \] that contain $T$. For lower-dimensional or empty sets, this full-dimensional definition does not supply a minimum enclosing ellipsoid; a relative-affine-hull or degenerate-ellipsoid convention and corresponding admissibility conditions on $S$ and $X$ are missing.

There is also a substantive distance ambiguity. Under the usual multiplicative affine Banach--Mazur convention, distances are at least $1$, and any two nondegenerate ellipsoids have distance $1$, since they are affinely equivalent. Thus the displayed comparison cannot express a nontrivial approximation of one such ellipsoid by another under that convention. A logarithmic convention changes the baseline but still assigns distance zero to affinely equivalent ellipsoids. The record does not specify a comparison retaining their relative position and shape, a different normalization, or another intended definition. No replacement of $\varepsilon$ by $1+\varepsilon$, or replacement of the distance, is made here. The admissible range of $\varepsilon$, the convention for a minimum over an empty admissible family, and the parameter range and uniformity intended by the $O$-bound also require clarification.

Short English statement

The record asks two separate questions: whether convex-cell partitions of ${\mathbb{R}}^3$ can have arbitrarily large incidence counts at every cell and vertex, and whether subsets of size $O(d/\varepsilon^2)$ suffice for the stated comparison of minimum enclosing ellipsoids. The partition conventions and ellipsoid comparison are insufficiently specified; ordinary affine Banach--Mazur distance makes all nondegenerate ellipsoids equivalent. Both questions therefore require clarification and human mathematical review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30001899$, title "High Incidence Partitions and Minimum Ellipsoid Coresets," exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is named; the supplied proposed year is $2011$.
• Supplied report citation: Discrete Geometry (2012), Oberwolfach Reports, pp. 2459--2548, DOI 10.4171/owr/2011/44. Supplied source URL and literature-source link labeled "OWR 44 (2012)": https://doi.org/10.4171/owr/2011/44. The background describes Oberwolfach Reports as documenting workshops and their open-problem discussions. The bibliographic details are reproduced as supplied.
• Supplied literature-source link labeled "Clarkson coreset notes": https://kenclarkson.org/paris_school/t.html.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the record open and states that the report poses both questions and that related coreset estimates do not settle the combined formulation. This is supplied dated curation, not an independently verified literature assessment; the background explicitly requests independent verification of time-sensitive status and cited claims.
• The registry supplies the statement-status label corrected_verified and reports that the official report was checked and the ellipsoid subset function explicitly defined. These are supplied verification claims, not verification performed for this draft. No source was visited in preparing this statement.