Partitioning a planar assembly into two connected parts is NP-complete
From MaRDI portal
Publication:672026
DOI10.1016/0020-0190(95)00083-OzbMath0875.68536OpenAlexW2086001589MaRDI QIDQ672026
Lydia E. Kavraki, Mihail N. Kolountzakis
Publication date: 27 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(95)00083-o
Related Items
On the separability of quadrilaterals in the plane by translations and rotations ⋮ Intractability of assembly sequencing: Unit disks in the plane ⋮ On the complexity of one-shot translational separability.
Cites Work
- Unnamed Item
- Unnamed Item
- Separating two simple polygons by a sequence of translations
- On the complexity of assembly partitioning
- Objects that cannot be taken apart with two hands
- On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
- DISASSEMBLING TWO-DIMENSIONAL COMPOSITE PARTS VIA TRANSLATIONS
