Discrete Geometry and Convexity in the Max-Plus Algebra

20 concepts7 papers3 proposals

What happens to geometry when you change the rules of arithmetic? In classical geometry, we operate in a world governed by addition and multiplication. But if we replace these standard operations with alternative algebraic rules, familiar geometric landscapes—lines, polyhedra, and convex hulls—warp into entirely new structures.

This is the core premise of tropical geometry and max-plus algebra. By replacing standard addition with the maximum operator ($\oplus = \max$) and standard multiplication with addition ($\otimes = +$), researchers have uncovered a parallel geometric universe. Over the past few decades, a major research direction has emerged to determine exactly how much of classical discrete geometry survives this algebraic translation, where the analogies break down, and how this alternative framework can solve notoriously difficult problems in optimization and game theory.

The Max-Plus Mirror: Redefining Convexity

To understand why this framework works, consider how convexity changes. In classical Euclidean space, a set is convex if, for any two points, it contains the straight line segment connecting them. This segment is formed by taking linear combinations $\lambda x + (1-\lambda)y$ where the weights sum to one.

In the max-plus world, a tropical linear combination of two points $x$ and $y$ takes the form: $$\max(\lambda + x, \mu + y)$$ where $\lambda$ and $\mu$ act as the tropical scalar weights. Because the $\max$ function only changes values when its arguments cross, a "tropical line segment" is not a straight line. Instead, it is a rigid, piecewise-linear path composed of orthogonal segments.

Despite this jagged appearance, these structures behave remarkably like classical polyhedra. As explored by Xavier Allamigeon et al., defining fundamental properties like "extreme points" and "polyhedra" within the max-plus framework allows researchers to test the boundaries of classical discrete geometry. For instance, the authors investigated whether McMullen’s upper bound theorem—which limits the number of extreme points a classical polyhedron can have based on its dimension and number of facets—holds in the tropical setting. By mapping tropical polyhedra to lattice path counting, they demonstrated that a tropical analogue of this bound does indeed exist.

Why Core Combinatorial Theorems Transfer

Remarkably, many of the foundational pillars of discrete geometry pass through the max-plus mirror completely intact. In classical geometry, theorems by Carathéodory, Helly, Radon, and Tverberg dictate how convex sets intersect and how points can be partitioned.

In Carathéodory, Helly and the Others in the Max-Plus World, Stephane Gaubert et al. systematically demonstrated that these deep geometric principles have direct max-plus analogues. Why do these theorems transfer so cleanly? The intuition lies in the nature of the max-plus operations themselves. Because the maximum operator is inherently about order, selection, and comparison, max-plus arithmetic is deeply combinatorial. The authors showed that classical proof techniques—such as induction, bipartite graph theory, and combinatorial partitioning—remain highly effective when adapted to the max-plus framework.

In fact, the max-plus framework can sometimes simplify problems that are intractable in Euclidean space. The authors proved that Sierksma’s conjecture (which concerns the number of possible Tverberg partitions) is true within the max-plus setting, even though it remains an open, unresolved problem in standard discrete geometry. However, this success highlights a fascinating disconnect: because the algebraic structures differ, proving a theorem in the max-plus world does not automatically validate it in the classical world.

The Tropical-Classical Gap: Where the Analogy Breaks Down

The translation is not always seamless. Classical discrete geometry relies heavily on topology—the mathematics of continuous deformations, smooth boundaries, and fixed-point theorems. The max-plus world, by contrast, is rigid, discrete, and piecewise-linear. This creates a structural gap where classical topological proof strategies fail.

This limitation is vividly illustrated in Tropical Carathéodory with Matroids. Georg Loho et al. examined the Colorful Carathéodory Theorem in the tropical setting. In Euclidean space, this theorem is typically proven using standard topological methods. The authors demonstrated that these topological approaches are fundamentally incompatible with the piecewise-linear environment of tropical convex hulls. To bridge this gap, they had to abandon classical topology entirely and construct a new framework rooted in matroid theory, proving that the theorem could instead be sustained by purely combinatorial structures.

Furthermore, moving from classical space to tropical space often requires a process called tropicalization, which can cause structural information to vanish. In Signed Tropicalization of Polar Cones, Xavier Allamigeon et al. attempted to translate "polar cones"—a concept fundamental to optimization and duality—into a signed tropical domain. The authors discovered that tropicalizing classical matrix cones causes complex geometric hierarchies to collapse. This collapse reveals an inherent loss of information, demonstrating that while tropical analogues provide powerful new tools, they also flatten some of the intricate geometry present in Euclidean space.

Algorithmic Payoffs: Optimization and Complexity

Why endure the mathematical friction of translating geometry into the max-plus language? The answer lies in the massive algorithmic leverage it provides for solving optimization, control, and machine learning problems, as noted by Michael Breuß et al.. By viewing classical optimization problems through a tropical lens, researchers can expose the underlying combinatorial skeletons of complex algorithms.

A prime example is the study of linear programming. In Combinatorial Simplex Algorithms Can Solve Mean Payoff Games, Xavier Allamigeon et al. used tropical polyhedra to build a bridge between linear programming and game theory. They developed a tropical implementation of the simplex method using a novel symbolic perturbation scheme to handle degenerate inputs. This allowed them to prove a profound algorithmic connection: if a strongly polynomial combinatorial pivoting rule exists for classical linear programming, then mean payoff games can also be solved in strongly polynomial time.

Conversely, tropical geometry can be used to expose the fundamental limitations of classical optimization algorithms. For decades, researchers have tried to determine whether certain interior-point methods for linear programming run in strongly polynomial time. In Short-step methods are not strongly polynomial-time, Manru Zong et al. settled this for a broad class of "short-step" methods. They did this by drawing upon tropical geometry to construct specific, pathological linear programs with "ill-behaved" central paths. The tropical perspective allowed them to prove that these paths twist in ways that force the algorithm to take a number of steps that grows unboundedly with the problem size, shattering the possibility of a strongly polynomial runtime bound for these methods.

By treating the max-plus algebra not merely as a curiosity, but as a distinct geometric domain, this research direction continues to illuminate the deep boundaries between continuous topology, discrete combinatorics, and computational complexity.

Key Foundational Work

Carathéodory, Helly and the Others in the Max-Plus World (2010) — contributed 12 concept elements to this direction.
The number of extreme points of tropical polyhedra (2011) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_max_plus_analogues_of_advanced_discrete__497dbf3c,
  title = {max-plus analogues of advanced discrete geometry theorems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/max-plus-analogues-of-advanced-discrete-geometry-theorems/rdr_497dbf3c456a4e0c89e96bc99e63dcb6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_max_plus_analogues_of_advanced_discrete__497dbf3c_v1,
  title = {max-plus analogues of advanced discrete geometry theorems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/max-plus-analogues-of-advanced-discrete-geometry-theorems/rdr_497dbf3c456a4e0c89e96bc99e63dcb6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake