🔢 mathematics

Algebraic Distance Optimization in Polyhedral Norms

This paper investigates the distance minimization problem to a real algebraic variety under a polyhedral norm by proving that the variety admits a semialgebraic stratification based on the dimension of Voronoi cones and providing an algebraic description of the associated medial axis.

Original authors: Eliana Duarte, Nidhi Kaihnsa, Julia Lindberg, Angélica Torres, Madeleine Weinstein

Published 2026-04-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Eliana Duarte, Nidhi Kaihnsa, Julia Lindberg, Angélica Torres, Madeleine Weinstein

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are standing in a vast, foggy field (this is your data space). In the middle of the field, there is a mysterious, invisible fence made of algebraic curves and surfaces (this is your algebraic variety, or the "model" you are trying to fit). You drop a ball (a data point) somewhere in the fog.

The big question in data science is: Where on the fence is this ball closest to? Usually, we measure distance in the standard way (like a straight line, or "Euclidean" distance). But in this paper, the authors ask a different question: What happens if we measure distance using a weird, blocky ruler instead of a straight ruler?

Here is a breakdown of their work using simple analogies:

1. The "Blocky" Ruler (Polyhedral Norms)

In our daily lives, we measure distance with a straight line. But imagine if your ruler was shaped like a cube or a diamond instead of a circle.

The Analogy: Think of the "unit ball" (the shape that defines "distance 1") as a Lego brick or a dice.
The Effect: If you are standing next to a wall and you measure distance using a cube-shaped ruler, the "closest point" might not be the point directly in front of you. It might be a corner or an edge of the wall, depending on how you tilt your cube.
Why it matters: This isn't just a math game. In fields like optimal transport (moving goods from warehouses to stores), the "cost" of moving isn't always a straight line. Sometimes it's cheaper to move along a grid (like city streets). This paper studies what happens when your "distance" is defined by these blocky, grid-like rules.

2. The "Voronoi Cell" (The Territory of a Point)

Usually, if you have a few points on a map, you can draw lines to divide the map into territories. Everyone in "Territory A" is closest to Point A. This is called a Voronoi diagram.

The Paper's Twist: The authors ask: "If our fence is a complex algebraic curve (like a twisted ribbon), and we use our blocky ruler, what does the territory of a single point on that ribbon look like?"
The Discovery: They found that the territory isn't just a simple shape. It's a cone (like an ice cream cone) that depends on the local shape of the fence and the shape of your blocky ruler.
- If the fence is smooth and flat at that spot, the territory is a specific cone.
- If the fence is curved or twisted, the territory changes shape.
- They proved that you can predict the shape of this territory just by looking at how the "normal vector" (the direction pointing straight out from the fence) lines up with the corners and edges of your blocky ruler.

3. The "Stratification" (Sorting the Fence)

Imagine walking along that twisted ribbon fence. Sometimes the ribbon is flat, sometimes it's steep, and sometimes it's twisted in a way that makes the "blocky ruler" behave differently.

The Problem: You can't describe the whole fence with one simple rule because the "territories" change as you walk along it.
The Solution: The authors developed a way to slice the fence into layers (strata).
- Layer 1: Points where the territory is a big, wide cone (like a flat plain).
- Layer 2: Points where the territory is a thinner, sharper cone (like a sharp ridge).
- Layer 3: Points where the territory is just a single point (like a sharp peak).
Why it's cool: They proved that these layers are mathematically "clean" (semialgebraic sets). This means you can write down a set of equations to find exactly which part of the fence belongs to which layer. It's like having a map that tells you, "If you are in this red zone, your data point will be explained by a corner of the cube; if you are in this blue zone, it will be explained by an edge."

4. The "Medial Axis" (The Zone of Confusion)

Finally, they looked at the Medial Axis. This is the set of points in the fog where you are equally close to two (or more) different spots on the fence.

The Analogy: Imagine you are standing in the middle of a canyon. You are equally far from the left wall and the right wall. That line down the middle is the medial axis.
The Blocky Twist: With a blocky ruler, this "line of confusion" can get weird. It might be a flat sheet, a line, or a complex web.
The Result: The authors figured out how to calculate the "degree" (a measure of complexity) of these confusing zones.
- If the fence is a simple curve (degree $d$ ), the confusing zone isn't infinitely complex. They proved it has a maximum complexity of roughly $d^2$ .
- They showed that if the fence has "flat spots" that match the flat sides of your blocky ruler, the confusion zone can get huge (even filling up the whole space!).

Summary: Why Should You Care?

This paper is like a manual for navigating a world with blocky rules.

For Data Scientists: If you are using "blocky" distance metrics (common in machine learning and logistics), this tells you exactly how your data points will cluster around your models.
For Mathematicians: They took a messy, complex problem (distance to a curved shape with a weird ruler) and broke it down into neat, solvable layers.
The Big Picture: They showed that even when the rules of geometry get weird (using cubes instead of circles), there is still an underlying order. You can map out the "territories" of every point on a curve and predict exactly where the "confusion zones" (medial axes) will be.

In short: They figured out how to draw the map of a world where the ruler is a dice, ensuring we know exactly which point on the model explains our data best.

1. Problem Statement

The paper addresses the distance minimization problem for a real algebraic variety $X \subseteq \mathbb{R}^n$ under a polyhedral norm (a norm whose unit ball is a centrally symmetric convex polytope), rather than the standard Euclidean norm.

The core questions investigated are:

Inverse Problem: Given a point $p \in X$ , which points in $\mathbb{R}^n$ have $p$ as their unique closest point on $X$ ? The set of such points is the Voronoi cell of $p$ .
Stratification: How does the geometry of these Voronoi cells change as $p$ moves along the variety $X$ ? Specifically, for codimension-one varieties, the authors aim to decompose $X$ into strata based on the expected dimension of the Voronoi cells.
Medial Axis: What is the algebraic structure of the medial axis (the locus of points in $\mathbb{R}^n$ equidistant to at least two distinct points on $X$ )? The authors seek an algebraic description and degree bounds for its components.

2. Methodology

The authors combine tools from polyhedral geometry, differential topology, and real algebraic geometry.

Polyhedral Geometry & Duality:
- They utilize the inner normal fan $\Sigma_B$ of the unit ball $B$ .
- They define the type of a point $v \in X$ as the set of faces of $B$ whose inner normal cones intersect the normal space $N_v$ of the variety at $v$ .
- They establish a duality relationship: The Voronoi cone of $v$ is contained in the union of cones generated by the dual faces of the faces in the type of $v$ .
Stratification via Transversality:
- For codimension-one varieties, the normal space is 1-dimensional. The authors map the normal vectors to the real projective space $\mathbb{RP}^{n-1}$ .
- They define a stratification of $\mathbb{RP}^{n-1}$ based on the dimensions of the faces of the polyhedral ball.
- Using the Preimage Theorem from differential topology, they prove that if the map from the variety to the projective space is transverse to this stratification, the variety $X$ inherits a stratification where each stratum consists of points with Voronoi cones of a specific dimension.
- They prove these strata are semialgebraic sets.
Algebraic Description of the Medial Axis:
- They construct an equidistant ideal $I_{Eq}$ by considering pairs of faces $(F_1, F_2)$ of the unit ball.
- For a pair of faces, they define an ideal $J_{(F_1, F_2)}$ $J_{(F_{1}, F_{2})}$ generated by:
  1. The defining polynomial of the variety $f(x)=0$ (and $f(y)=0$ ).
  2. Linear equations enforcing that the distance is realized on faces $F_1$ and $F_2$ .
  3. Rank conditions (minors) ensuring the gradient of $f$ aligns with the normal vectors of the faces (tangency conditions).
- They compute the elimination ideal $I_{(F_1, F_2)}$ by eliminating variables $x, y, \lambda$ to obtain equations purely in the coordinates of the equidistant point $u$ .
- The medial axis is contained within the variety defined by the intersection of these elimination ideals over all face pairs.

3. Key Contributions and Results

A. Voronoi Cones and Types

Theorem 3.6: Characterizes the type of a smooth point $v$ on a variety $X$ as the set of faces $F$ of the unit ball $B$ such that the normal space $N_v$ intersects the dual face $F^*$ .
Voronoi Cone Containment: The Voronoi cell of a point $v$ is contained in the union of cones $C_v(B^*, F^*)$ for all $F$ in the type of $v$ . This generalizes the Euclidean result where the Voronoi cell lies in the normal space.
Optimizing Faces: They distinguish between the "type" (geometric intersection) and "optimizing faces" (faces where the distance is actually minimized). They show that for certain saddle points, the set of optimizing faces may be empty even if the type is non-empty.

B. Stratification of Codimension-One Varieties

Theorem 4.4: Proves that a smooth, connected, codimension-one variety $X$ $X$ can be stratified into semialgebraic sets $X_i$ $X_{i}$ based on the dimension of the Voronoi cones.
- Points in stratum $X_i$ have Voronoi cones of dimension $n-i$ .
- The strata are defined by the intersection of the normal map with the stratification of $\mathbb{RP}^{n-1}$ .
Semialgebraicity: Theorem 4.8 confirms that each stratum $X_i$ is a semialgebraic set, providing an explicit algebraic description using the Tarski-Seidenberg theorem.

C. The Medial Axis and Degree Bounds

Algebraic Containment: Theorem 5.5 establishes that the algebraic closure of the medial axis $M_X$ is contained in the variety $V(I_{Eq})$ defined by the equidistant ideal.
Degree Bounds: The paper provides specific degree bounds for the components of the medial axis based on the types of faces $(F_1, F_2)$ $(F_{1}, F_{2})$ involved in the equidistance:
- Two Vertices (Theorem 5.11): If $F_1, F_2$ are vertices, the degree of the component is at most $d^2 - d$ (where $d = \deg(f)$ ).
- Vertex and Facet (Theorem 5.12): If $F_1$ is a vertex and $F_2$ is a facet, the degree is bounded by $d$ .
- Two Facets (Theorem 5.13): If $F_1, F_2$ are facets, the degree is bounded by $s \cdot t$ , where $s$ and $t$ are the number of points on $X$ with tangent spaces parallel to $F_1$ and $F_2$ , respectively.
Quadratic Varieties: For quadratic varieties ( $d=2$ ), the degree of any component of the medial axis is at most 4.

4. Significance and Applications

Generalization of Euclidean Results: This work extends the well-studied theory of Voronoi diagrams and medial axes from Euclidean metrics to polyhedral norms. This is crucial for applications where the underlying metric is non-Euclidean, such as in optimal transport (Wasserstein distance) and Lipschitz polytopes.
Computational Algebraic Geometry: By providing explicit degree bounds and semialgebraic descriptions, the paper enables the use of computational tools (like Gröbner bases) to compute Voronoi diagrams and medial axes for specific algebraic models.
Machine Learning and Statistics: The results are relevant to algebraic statistics and machine learning, where distance minimization to algebraic models is a fundamental step in parameter estimation and model fitting. Understanding the geometry of the medial axis helps in analyzing the stability and ambiguity of these estimations.
Geometric Insight: The stratification approach reveals that the "complexity" of the distance optimization problem (in terms of the dimension of the solution space) is locally constant on semialgebraic sets, allowing for a piecewise analysis of the problem.

5. Conclusion

The paper successfully bridges polyhedral geometry and algebraic geometry to solve distance optimization problems under polyhedral norms. It provides a rigorous framework for decomposing varieties into strata based on Voronoi cell dimensions and offers concrete algebraic bounds for the medial axis, laying the groundwork for algorithmic computation in non-Euclidean settings.