Minimum Boundary Touching Tilings of Simple Polyominoes

by    A. Spillner

Preprint series: 04-13, Reports on Computer Science

MSC:
68U05 Computer graphics; computational geometry [See also 65D18]
65D18 Computer graphics and computational geometry [See also 51N05, 68U05]

Abstract: We continue to study the problem
of tiling a polyominoe \(P\) with
squares such that every square in
the tiling has a nonempty
intersection with the boundary of
\(P\). In this paper we describe
a pseudopolynomial time algorithm
which given a simple polyominoe
\(P\) computes a tiling of \(P\)
with the minimum number of squares.

Keywords: polyomino, tiling

Upload: 2004-12-22


The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.