On the hardness of computing intersection, union and Minkowski sum of polytopes
type: Item
instance of: scholarly article
title: On the hardness of computing intersection, union and Minkowski sum of polytopes
zbMATH Open document ID: 1155.52008
author: Hans Raj Tiwary
published in: Discrete \& Computational Geometry
publication date: 2008-12-02T00:00:00Z
review text: For polytopes \(P_1\), \(P_2\subset \mathbb R^d\), the author considers the intersection \(P_1\cap P_2\), the convex hull of the union \(CH(P_1\cup P_2)\) and the Minkowski sum \(P_1 +P_2\). The principal aim is to analyze the algorithmic complexity of performing these operations and providing a nonredundant description of resulting polytopes. For the Minkowski sum, it is demonstrated that enumerating the facets of \(P_1 +P_2\) is \(NP\)-hard if \(P_1\), \(P_2\) are represented by facets, or if \(P_1\) is specified by vertices and \(P_2\) is a polyhedral cone specified by facets. For the intersection, it is demonstrated that computing the facets or the vertices of \(P_1\cap P_2\) is \(NP\)-hard if one of \(P_1\), \(P_2\) is given by vertices and the other by facets. Besides, computing the vertices of \(P_1\cap P_2\) is \(NP\)-hard if \(P_1\), \(P_2\) are represented by vertices. Because of the polar duality, similar results hold for the convex hull of the union of polytopes.
Mathematics Subject Classification ID: 52B11
Mathematics Subject Classification ID: 52B05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 5377165
zbMATH Keywords: polytope
zbMATH Keywords: Minkowski sum
zbMATH Keywords: convex hull
zbMATH Keywords: Turing reduction
reviewed by: Vasyl Gorkaviy
MaRDI profile type: Publication
full work available at URL: s00454-008-9097-3
OpenAlex ID: W2000147742
cites work: How good are convex hull algorithms?
cites work: On the convex hull of the union of certain polyhedra
cites work: On the complexity of four polyhedral set containment problems
cites work: From the zonotope construction to the Minkowski addition of convex polytopes
cites work: Extended convex hull
cites work: \(f\)-vectors of Minkowski additions of convex polytopes
cites work: Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
cites work: Geometric algorithms and combinatorial optimization.
cites work: Q4434671
cites work: The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings
cites work: Generating all vertices of a polyhedron is hard
cites work: Q4197641
cites work: On the Newton polytope of the resultant
cites work: Q4953977
cites work: Lectures on Polytopes
DOI: 10.1007/S00454-008-9097-3
description: scientific article; zbMATH DE number 5377165