För polytoper P 1, P 2  på R d anser vi skärningspunkten P 1 P 2, konvexa skrovet av unionen CH (P1 P2) och Minkowski summan P1 + P2. För Minkowski-summan bevisar vi att uppräkning av facetter av P1 +P2 är NPhard om P 1 och P 2 anges av facetter, eller om P 1 anges av hörn och P2 är en polyhedral kon specificerad av facetter. För skärningspunkten bevisar vi att beräkning av fasetter eller hörn i skärningspunkten mellan två polytoper är NP-hård om en av dem ges av hörn och den andra av fasetter. Dessutom, beräkning hörn av skärningspunkten mellan två polytoper som ges av hörn visas vara NP-hård. Analoga resultat för beräkning av konvexa skrov av föreningen av två polytoper följer från polar dualitet. Alla hårdhetsresultat etableras genom att visa att den lämpliga beslutsversionen, för vart och ett av dessa problem, är NP-fullständig.
Tiwary REF visade att avgörandet om en H-polytop är likvärdig med konvexa skrovet eller Minkowski summan av två H-polytoper är co-NP-komplett.
On the hardness of computing intersection, union and minkowski sum of polytopes
{'venue': 'DISCRETE & COMPUTATIONAL GEOMETRY', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}