On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes

By Hans Raj Tiwary. 2008

123 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Discrete Mathematics and Combinatorics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. René Vidal
2. Tom Diethe
3. Joseph K. Scott
4. Paris V. Giampouras
5. Jeremias Knoblauch
6. Hisham Husain
7. Liangzu Peng

In Computer Graphics and Computer-Aided Design

1. René Vidal
2. Tom Diethe
3. Jeremias Knoblauch
4. Hisham Husain

In Discrete Mathematics and Combinatorics

1. René Vidal
2. Tom Diethe
3. Jeremias Knoblauch
4. Hisham Husain

Citations in the corpus

• The Ideal Continual Learner: An Agent That Never Forgets (2023, background): “Note that verifying whether ∩t=1Gt is empty or not is in general NP-hard even when every Gt is a “simple” polytope (Tiwary, 2008), which is the main reason that Knoblauch”
• Optimal Continual Learning has Perfect Memory and is NP-hard (2020, methodology): “If S is the set of polytopes, the same conclusion is reached by using the re-sults of Tiwary (2008a) and Tiwary (2008b).”
• A Geometric Approach to Aggregate Flexibility Modeling of Thermostatically Controlled Loads (2016, background): “In fact, calculating the Minkowski sum of two sets Q1 and Q2 when they are polytopes specified by facets is NP-hard since the facets of the obtained polytope can grow exponentially with the number of the facets of Q1 and Q2 [30], [31].”
• Constrained zonotopes: A new tool for set-based estimation and fault detection (2016, background): “However, the complexity of (5) is exponential in n, as is the worst-case number of halfspaces describing Z + W (Hagemann, 2015; Tiwary, 2008).”