Result · D-GLOBAL-XP

Exact D search is polynomial at fixed dimension and bin count

Proved herepublication: internal

Meaning

The geometric structure yields an XP complexity bound; the polynomial exponent depends on dimension and bin count.

Scientific context

Because every global optimum is realizable as a nearest-centre labelling (D-GLOBAL-GEOMETRIC-REALIZABILITY), an arrangement enumeration solves the finite determinant problem exactly, in time polynomial in the sample size for a fixed parameter dimension and cell count. This is a direct application of a known enumeration template rather than a new algorithmic idea; whether the resulting exponent is tight is a separate, open question (OPEN-D-PARAMETERIZED-COMPLEXITY).

Statement

Because global optima are affine/Voronoi-realizable, arrangement enumeration yields an exact algorithm N^{O(Kd)} for fixed d and K.

Where it stops

This is XP-style, not an FPT result; hardness and tightness remain open.

Relationships

Rests on

Every finite global D optimum is geometrically realizableD-GLOBAL-GEOMETRIC-REALIZABILITY

The full chain beneath it

Enables

Parameterized complexity of global finite D quantizationOPEN-D-PARAMETERIZED-COMPLEXITY

Raises

Parameterized complexity of global finite D quantizationOPEN-D-PARAMETERIZED-COMPLEXITY

Open next door

Local graph

Prerequisites to the left, what it enables or raises to the right, boundary cases below. Open in the map.

Proof

D11. Exact global enumeration for fixed $(d,K)$

D7 restricts candidate global labelings to affine-max-realizable partitions. Arrangement enumeration gives an exact XP algorithm of form

\boxed{N^{O(Kd)}}

for fixed $(d,K)$ , with an effective affine parameter count of order $(K-1)(d+1)$ .

This is an application of a known computational-geometry template; hardness/FPT status remains open.

From D-optimality · chapter contents