ylfink@water.UUCP (09/23/87)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
THEORY SEMINAR
- Thursday, September 24, 1987
Professor Maurice Nivat visiting the Department of
Computer Science, will speak on ``Some New Results
About Tiling the Plane''.
TIME: 3:30 PM
ROOM: MC 6091A
ABSTRACT
The tiles we consider are polyominoes or connected
subsets of unit squares which contain no hole. Given a
finite set of finite tiles of this kind, which can be
only translated but are in infinite supply, it is
undecidable whether
- there exists a rectangle which can be exactly
covered using these tiles,
- there exists a figure of any shape which can be
covered in two different ways.
We characterize the tiles which are exact, that is, the
whole plane can be covered by such a tile alone: a
tile is exact iff it is a pseudo-parallelogram which
means that there exists four points x , x , x , x on
- - - -
1 2 3 4
the border satisfying
- the vectors x , x and x , x are equal (so
- - - -
1 4 2 3
that x , x , x , x are indeed the vertices of
- - - -
1 2 3 4
a real parallelogram,
- the segments [x , x ] and [x , x ] of the
- - - -
2 4 2 3
border are equal (these segments are words on
- -
{h, h, v, v} representing the broken line from
-- - - --
September 22, 1987
- 2 -
one point to another),
- the segments [x , x ] and [x , x ] are
- - - -
1 2 4 3
conjugate words.
September 22, 1987