Dimensional uniform rasterizability
DefinitionBeyondConvexity_APTAS_Supplement_UniformRasterizablecomputational-geometryoperations-researchp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1theoretical-computer-science
A grid with real side and arbitrary real phase has closed hypercubic cells indexed by . Its cover is the union of cells whose interiors meet the interior of . Uniform rasterizability requires one rational-valued polynomial-time resolution with for rational , such that for every valid class region , every real translation , every phase and every real ,
Volumes are extended nonnegative reals; valid finite simplicial regions and these covers have finite volume. The resolution machine operates on finite rational encodings; placements, phases and real scales are analytic quantifiers. This is the higher-dimensional version of Definitions 2 and 3, without an assumed bulk inequality.
Definition code
import Definitions.Def_BeyondConvexity_APTAS_Supplement_PolyhedralRegion
noncomputable section
namespace BeyondConvexity.APTAS.Supplement
def gridCell {d : ℕ} (h : ℝ) (τ : RPoint d) (z : Fin d → ℤ) : Set (RPoint d) :=
{x | ∀ i, τ i + (z i : ℝ) * h ≤ x i ∧ x i ≤ τ i + ((z i : ℝ) + 1) * h}
def gridCover {d : ℕ} (h : ℝ) (τ : RPoint d) (S : Set (RPoint d)) : Set (RPoint d) :=
⋃ z : Fin d → ℤ, ⋃ (_ : (interior (gridCell h τ z) ∩ interior S).Nonempty),
gridCell h τ z
/-- Definition 3 in dimension d. Every placement, phase and positive real scale
is quantified; the machine computes only the rational resolution. -/
def UniformRasterizable {d : ℕ} (P : Set (PolyhedralRegion d)) : Prop :=
∃ resolution : ℚ → ℚ,
PolynomialOn AbelianCayleyHDX.encRat AbelianCayleyHDX.encRat
(fun η => 0 < η ∧ η < 1) resolution ∧
(∀ η : ℚ, 0 < η → η < 1 → 0 < resolution η ∧ resolution η ≤ 1) ∧
∀ η : ℚ, 0 < η → η < 1 → ∀ Q ∈ P, Q.Valid →
∀ (v τ : RPoint d) (h : ℝ), 0 < h → h ≤ (resolution η : ℝ) * Q.span →
vol (gridCover h τ (translate v Q.region) \ translate v Q.region) ≤
ENNReal.ofReal (η : ℝ) * vol Q.region
end BeyondConvexity.APTAS.Supplement
Source
Lucas de Oliveira Silva, Elisa Dell'Arriva, Flávio Keidi Miyazawa, STOC 2027 submission #890 (October 2026), Definitions 2-3, printed pp.5-6 / PDF pp.6-7; Section 7, printed p.16 / PDF p.17