Minkowski Sum

Geometric operation underlying No-Fit Polygon computation.

Also called: Minkowski Sum · 민코프스키 덧셈

A geometry primitive: $A \oplus B = \{a + b : a \in A, b \in B\}$ . In nesting it is the computational basis of the No-Fit Polygon — the NFP of two pieces is the Minkowski sum of one piece with the reflection of the other.

Claims & evidence

Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.

A–X describes evidence reliability; E0–E4 describes mathematical similarity between problems. The two axes are independent.

Relationships from this entry 1

shares method with
Minkowski Sum to No-Fit Polygon
The No-Fit Polygon of A and B equals the Minkowski sum of A and the reflection (−B); computing the NFP is computing a Minkowski sum.
EvidenceA · Peer-reviewed / official
Equiv.E0 · near-identical formulation
Sources
- Source grade: A — Peer-reviewed / officialThe geometry of nesting problems: A tutorial
  Citation details
  Bennell, J.A., Oliveira, J.F. (2008). The geometry of nesting problems: A tutorial. EJOR 184(2):397-415.

Relationships from this entry
Relationship	Claim	Evidence	Equiv.	Sources
shares method with Minkowski Sum to No-Fit Polygon	The No-Fit Polygon of A and B equals the Minkowski sum of A and the reflection (−B); computing the NFP is computing a Minkowski sum.	A · Peer-reviewed / official	E0 · near-identical formulation	Source grade: A — Peer-reviewed / officialThe geometry of nesting problems: A tutorial Citation details Bennell, J.A., Oliveira, J.F. (2008). The geometry of nesting problems: A tutorial. EJOR 184(2):397-415.

Relationships to this entry 1

uses method
2D Irregular Nesting to Minkowski Sum
Because the No-Fit Polygon used for overlap testing is computed as a Minkowski sum, irregular nesting directly relies on the Minkowski sum.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialThe geometry of nesting problems: A tutorial
  Citation details
  Bennell, J.A., Oliveira, J.F. (2008). The geometry of nesting problems: A tutorial. EJOR 184(2):397-415.

Relationships to this entry
Relationship	Claim	Evidence	Equiv.	Sources
uses method 2D Irregular Nesting to Minkowski Sum	Because the No-Fit Polygon used for overlap testing is computed as a Minkowski sum, irregular nesting directly relies on the Minkowski sum.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialThe geometry of nesting problems: A tutorial Citation details Bennell, J.A., Oliveira, J.F. (2008). The geometry of nesting problems: A tutorial. EJOR 184(2):397-415.