PARTITIONING A PLANAR ASSEMBLY INTO 2 CONNECTED PARTS IS NP-COMPLETE

Authors
KAVRAKI LE KOLOUNTZAKIS MN
Citation
Le. Kavraki et Mn. Kolountzakis, PARTITIONING A PLANAR ASSEMBLY INTO 2 CONNECTED PARTS IS NP-COMPLETE, Information processing letters, 55(3), 1995, pp. 159-165
Citations number
17
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
55
Issue
3
Year of publication
1995
Pages
159 - 165
Database
ISI
SICI code
0020-0190(1995)55:3<159:PAPAI2>2.0.ZU;2-N
Abstract
Consider the following decision problem. Given a collection of non-ove rlapping (but possibly touching) polygons in the plane, is there a pro per connected subcollection of it that can be separated from its compl ement moving as a rigid body, without disturbing the other parts of th e collection, and such that the complement is also connected? We show that this decision problem is NP-complete. This had been known to be t rue without the connectedness requirement, and also with this requirem ent but in three-dimensional space.