# Directional Vertex Polytope Decoder

- ID: 205
- Canonical URL: https://synthcore.org/idea/205/directional-vertex-polytope-decoder
- API JSON: https://synthcore.org/api/idea/205.json
- API Markdown: https://synthcore.org/api/idea/205.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.26615](https://arxiv.org/abs/2608.26615)
- Category: architecture
- Solves: accuracy, scalability, stability
- ML areas: embedding, world-model, loss, regularization
- Math tags: convex-analysis, geometry, metric-geometry
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

## Idea description

Represent a predicted convex object by one point per prescribed unit direction and decode it as the convex hull of those points. Enforce direction-wise maximizer inequalities so every point is a genuine vertex, then use the covering-radius bound to choose the number and placement of directions according to the desired geometric accuracy.

## Mathematical statement

Let $a_1,\ldots,a_N\in S^{d-1}$ be fixed unit directions and let $\boldsymbol{x}=(x_1,\ldots,x_N)\in(\mathbb{R}^d)^N$. The admissible cone is $\mathcal{C}^{\flat}_{\boldsymbol{a}}=\{\boldsymbol{x}:a_i^T x_i\geq a_i^T x_j\ \forall i,j\}$; its interior is characterized by strict inequalities $a_i^T x_i>a_i^T x_j$ for every $i\neq j$, which guarantees that every $x_i$ is a distinct extremal point of $P=\operatorname{co}\{x_1,\ldots,x_N\}$. For any two point tuples, convexification is nonexpansive: $\operatorname{dist}(\operatorname{co}\{\boldsymbol{x}\},\operatorname{co}\{\boldsymbol{y}\})\leq\operatorname{dist}(\{\boldsymbol{x}\},\{\boldsymbol{y}\})$. For a target compact convex body $K$, define its support function $\sigma(K,u)=\max_{x\in K}u^T x$, its size $\|K\|=\max_{x\in K}\|x\|$, and the chordal covering radius $\delta_{\boldsymbol{a}}=\max_{u\in S^{d-1}}\min_i\|u-a_i\|$. Theorem 34 states that if $x_i\in\arg\max_{x\in K}a_i^T x$, then $P=\operatorname{co}\{x_1,\ldots,x_N\}$ satisfies $P\subseteq K$ and $\operatorname{dist}(K,P)\leq2\delta_{\boldsymbol{a}}\|K\|$.

## Key formulas

- $$\mathcal{C}^{\flat}_{\boldsymbol{a}}=\{(x_1,\ldots,x_N)\in(\mathbb{R}^d)^N:a_i^T x_i\geq a_i^T x_j\ \text{for all }i,j\},\qquad \operatorname{int}\mathcal{C}^{\flat}_{\boldsymbol{a}}=\{\boldsymbol{x}:a_i^T x_i>a_i^T x_j\ \forall i\neq j\}.$$
- $$P(\boldsymbol{x})=\operatorname{co}\{x_1,\ldots,x_N\},\qquad \operatorname{dist}(P(\boldsymbol{x}),P(\boldsymbol{y}))\leq\operatorname{dist}(\{\boldsymbol{x}\},\{\boldsymbol{y}\}).$$
- $$\delta_{\boldsymbol{a}}:=\max_{u\in S^{d-1}}\min_{1\leq i\leq N}\|u-a_i\|,\qquad \operatorname{dist}(K,P)\leq2\delta_{\boldsymbol{a}}\|K\|\quad\text{for }P\in\Pi^{\flat}_{\boldsymbol{a}}(K).$$
- $$\operatorname{dist}_H(K,L)=\sup_{u\in S^{d-1}}|\sigma(K,u)-\sigma(L,u)|,\qquad |\sigma(K,u)-\sigma(K,v)|\leq\|K\|\,\|u-v\|.$$

## Implementation notes

1. Integration point: use this as a decoder for a convex-valued latent variable in a VAE, world model, object-shape predictor, or graph output. Choose d as the object coordinate dimension and precompute N approximately uniform directions a_i on the sphere. The network outputs x_i in R^d for each direction. Decode P as the convex hull of the predicted points. 2. MVP update: let z be the raw network output and compute x by solving the quadratic program minimize 0.5 times the sum over i of ||x_i-z_i|| squared, subject to a_i transpose x_i minus a_i transpose x_j being at least epsilon for all i not equal to j. Use a differentiable QP layer, or initially replace it with the penalty lambda times the sum over i not equal to j of max(0, epsilon minus a_i transpose x_i plus a_i transpose x_j) squared. For a sampled query direction u, compute the predicted support value as max_i u transpose x_i and train against target support values or point clouds. 3. Compute the mathematical quantities exactly: cone violations, convex-hull support values, and the approximation certificate 2 delta times the object radius. Estimate delta numerically using a dense spherical grid or random directions. 4. First experiment: train a small MLP or VAE on two-dimensional convex shapes generated from random polygons, comparing this decoder with an unconstrained point-set decoder and a standard polygon decoder at N equal to 8, 16, and 32. Measure Hausdorff error, invalid outputs, support-function error, and training stability. Success is monotone error reduction as N increases, approximately tracking the bound 2 delta times the object radius, with zero nonconvex outputs and no worse equal-FLOP reconstruction loss.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: harms
- Verdict: Built a directional vertex-polytope decoder MVP with support-loss training, cone-violation penalty, covering-radius estimation, and analytic 2D sanity checks. For uniform directions, measured covering radii and cone margins matched the exact formulas to about 1e-6, and the inscribed-circle hull error decreased as N^-2 while the theorem certificate decreased as N^-1, confirming the stated bound and its looseness. In the learned comparison, the penalty decoder reduced but did not eliminate invalid outputs and had substantially worse support MSE than the unconstrained baseline, so no practical reconstruction win was demonstrated.

### Mechanism check

- Verdict: Built a directional vertex-polytope decoder MVP with support-loss training, cone-violation penalty, covering-radius estimation, and analytic 2D sanity checks. For uniform directions, measured covering radii and cone margins matched the exact formulas to about 1e-6, and the inscribed-circle hull error decreased as N^-2 while the theorem certificate decreased as N^-1, confirming the stated bound and its looseness. In the learned comparison, the penalty decoder reduced but did not eliminate invalid outputs and had substantially worse support MSE than the unconstrained baseline, so no practical reconstruction win was demonstrated.
- Confidence: 8/10
- Limitations: Only 2D analytic circles and a small synthetic ellipse-support regression were tested. The learned constraint used a soft penalty rather than an exact QP/projection layer; no VAE, point-cloud Hausdorff benchmark, FLOP-normalized training, higher-dimensional sphere designs, or formal differentiability/stability study was performed.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 0/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [bench_report.json](https://synthcore.org/code/104/bench_report.json)
- [custom_directional_polytope.py](https://synthcore.org/code/104/custom_directional_polytope.py)
- [experiment.py](https://synthcore.org/code/104/experiment.py)
- [report.md](https://synthcore.org/code/104/report.md)
- [report_bench_2026-08-30T142008.md](https://synthcore.org/code/104/report_bench_2026-08-30T142008.md)
- [results.json](https://synthcore.org/code/104/results.json)
- [run_bench.py](https://synthcore.org/code/104/run_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/104)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.