𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimum boundary touching tilings of polyominoes

✍ Scribed by Andreas Spillner

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
136 KB
Volume
52
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

Dedicated to Professor GΓΌnter Asser on the occasion of his eightieth birthday

We study the problem of tiling a polyomino P with as few squares as possible such that every square in the tiling has a non-empty intersection with the boundary of P . Our main result is an algorithm which given a simply connected polyomino P computes such a tiling of P . We indicate how one can improve the running time of this algorithm for the more restricted row-column-convex polyominoes. Finally we show that a related decision problem is in NP for rectangular polyominoes.

πŸ“œ SIMILAR VOLUMES

Analog neuro-based approach to tiling pr
Analog neuro-based approach to tiling problem using fitting function of polyominoes
✍ Hiroshi Ninomiya; Takeshi Nakayama; Hideki Asai πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 538 KB

The tiling problem is a typical NP-complete problem, where the polyominoes are to be arranged without a gap on a finite checkerboard. In this study, the arrangement of l polyominoes on an m u n checkerboard is considered. As the first step, the conventional parallel algorithm using the maximum neura

The boundaries of self-similar tiles in
The boundaries of self-similar tiles in Rn
✍ James Keesling πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 193 KB

Let K be a self-similar set in R n which has similarity dimension n and nonempty interior. In this paper it is shown that the topological boundary of K has Hausdorff dimension less than n. Examples are given to show that although the dimension of the boundary is strictly less than n, it may be arbit