A lower bound technique for triangulations of simplotopes

DOI10.1137/140972020zbMATH Open1381.52022OpenAlexW2962890073MaRDI QIDQ4601211FDOQ4601211

Authors Tyler Seacrest, Francis Edward Su

Publication date 12 January 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.1134

zbMATH Keywords

minimal triangulationsproducts of simplicessimplicial covers

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Abstract: Products of simplices, called simplotopes, and their triangulations arise naturally in algorithmic applications in game theory and optimization. We develop techniques to derive lower bounds for the size of simplicial covers and triangulations of simplotopes, including those with interior vertices. We establish that a minimal triangulation of a product of two simplices is given by a vertex triangulation, i.e., one without interior vertices. For products of more than two simplices, we produce bounds for products of segments and triangles. Aside from cubes, these are the first known lower bounds for triangulations of simplotopes with three or more factors, and our techniques suggest extensions to products of other kinds of simplices. We also construct a minimal triangulation of size 10 for the product of a triangle and a square using our lower bound.

Recommendations

• Lower bounds for simplicial covers and triangulations of cubes
• On minimal triangulations of products of convex polygons
• Approximation for minimum triangulations of simplicial convex 3-polytopes
• On simplicial partitions of polytopes
• Lower bounds for the simplexity of the \(n\)-cube

Cites work

• scientific article; zbMATH DE number 1372655 (Why is no real title available?)
• scientific article; zbMATH DE number 1860735 (Why is no real title available?)
• scientific article; zbMATH DE number 835749 (Why is no real title available?)
• A Simplicial Algorithm for Computing Robust Stationary Points of a Continuous Function on the Unit Simplex
• A lower bound for the simplexity of the \(n\)-cube via hyperbolic volumes
• A point set whose space of triangulations is disconnected
• A simple and relatively efficient triangulation of the n-cube
• A triangulation of the n-cube
• Asymptotically efficient triangulations of the \(d\)-cube
• Combinatorial Theorems on the Simplotope that Generalize Results on the Simplex and Cube
• Dyck path triangulations and extendability
• Flag arrangements and triangulations of products of simplices
• Graphs of transportation polytopes
• Lower bounds for simplicial covers and triangulations of cubes
• Minimal triangulation of the 4-cube
• On the Computation of Fixed Points in the Product Space of Unit Simplices and an Application to Noncooperative N Person Games
• Rental Harmony: Sperner's Lemma in Fair Division
• Simplexity of the cube
• The computation of fixed points and applications
• The geometry of products of minors
• Triangulations. Structures for algorithms and applications

Cited in

(8)

• A triangulation and fill-reducing initialization procedure for the simplex algorithm
• scientific article; zbMATH DE number 3883608 (Why is no real title available?)
• Almost Simplicial Polytopes: The Lower and Upper Bound Theorems
• On minimal triangulations of products of convex polygons
• Lower bounds for simplicial covers and triangulations of cubes
• An improved lower bound on the minimum number of triangulations
• Tractable relaxations of composite functions
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

Describes a project that uses

Uses Software

• TOPCOM

This page was built for publication: A lower bound technique for triangulations of simplotopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601211)