A lower bound technique for triangulations of simplotopes

DOI10.1137/140972020zbMATH Open1381.52022arXiv0910.1134OpenAlexW2962890073MaRDI QIDQ4601211FDOQ4601211

Authors: Tyler Seacrest, Francis Edward Su 

Publication date: 12 January 2018

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

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.

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

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

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)

Cites Work

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

Cited In (8)

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

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)