Extended formulations for polygons

DOI10.1007/s00454-012-9421-9zbMath1290.68122arXiv1107.0371MaRDI QIDQ714985

Samuel Fiorini, Hans Raj Tiwary, Thomas Rothvoß

Publication date: 15 October 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

polygon; polytope; lower bound; extended formulations

Mathematics Subject Classification ID

52B05: Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)