Complexity of Interlocking Polyominoes

Details Complexity of Interlocking Polyominoes Complexity of Interlocking Polyominoes

2011-12-17

arxiv.org/abs/1112.4087v1

Mathematics

Combinatorics

18 pages, 15 figures

Scientific paper

Polyominoes are a subset of polygons which can be constructed from integer-length squares fused at their edges. A system of polygons P is interlocked if no subset of the polygons in P can be removed arbitrarily far away from the rest. It is already known that polyominoes with four or fewer squares cannot interlock. It is also known that determining the interlockedness of polyominoes with an arbitrary number of squares is PSPACE hard. Here, we prove that a system of polyominoes with five or fewer squares cannot interlock, and that determining interlockedness of a system of polyominoes including hexominoes (polyominoes with six squares) or larger polyominoes is PSPACE hard.

Affiliated with

Also associated with

No associations

Rating

Complexity of Interlocking Polyominoes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity of Interlocking Polyominoes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Interlocking Polyominoes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-25536