Summary
The paper solves a longstanding math puzzle about how to break down complicated shapes called polyhedra into simpler parts in a way that is 'rational' or precise. The authors confirm an idea proposed by two mathematicians, Brlek and Reutenauer, linking special well-defined sets to previous results on how values can be assigned to these shapes. This helps unify different mathematical approaches to understanding polyhedra and their properties.
What this means in practice
- •For computational geometers: Use rational decompositions to improve algorithms that compute properties of polyhedra and related geometric objects.
- •For optimization engineers: Apply the clarified valuation structures of polyhedra in developing precise bounds and certificates for optimization problems involving polyhedral constraints.
A theory result. No direct application yet.
Authors
Flavio D'Alessandro, Paolo Papi
Abstract
We prove in the affirmative a conjecture of Brlek and Reutenauer (2003), which relates unambiguous rational sets to a well known result due to Khovanskii and Pukhlikov (1992) and independently to Lawrence (1990) on the valuations of the algebra spanned by the indicator functions of polyhedra.