Spine based construction of column-convex polyominoes
by
Goran Igaly
Department of Mathematics, University of Zagreb
Coauthors: Dragutin Svrtan (Department of Mathematics, University of Zagreb)

Unit square with all vertices at integer points in Cartesian plane is called cell. A polyomino is finite connected union of cells whose interior is also connected. Column-convex (or vertically convex) polyomino is polyomino in which all intersections with vertical lines are connected.

We will construct regular expression for coding the set of all column-convex polyominoes. This construction is based on spine of polyomino - the thin column-convex polyomino situated inside original polyomino. As one step of this construction, we will show one useful bijection on the collection of {-1, 0, 1}-walks on y-axis that preserves length of walk and number of its zero-steps.

Date received: March 20, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caex-43.