An Efficient Exhaustive Search Algorithm for the Escherization Problem
- PDF / 3,702,229 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 85 Downloads / 230 Views
An Efficient Exhaustive Search Algorithm for the Escherization Problem Yuichi Nagata1 · Shinji Imahori2 Received: 24 April 2018 / Accepted: 5 March 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In the Escherization problem, given a closed figure in the plane, the objective is to find a closed figure that is as close as possible to the input figure that tiles the plane. Koizumi and Sugihara’s formulation reduces this problem to an eigenvalue problem. In their formulation, only one of the potentially numerous templates is used to parameterize the possible tile shapes for each isohedral type. In this research, we try to search for the best tile shape using all possible templates for the nine most general isohedral types. This extension provides a considerable flexibility in possible tile shapes and improves the quality of the obtained tile shapes. However, the exhaustive search of all possible templates is computationally unrealistic using conventional calculation methods, and we develop an efficient algorithm to perform this in a reasonable computation time. Keywords Escherization · Escher-like tiling · Tessellation · Procrustes distance · Isohedral tiling
1 Introduction A tiling of the plane is a collection of shapes, called tiles, which cover the plane without any gaps or overlapping. Tiling has attracted much attention, owing to interest in both its practical and mathematical aspects. Tiling theory [6] is an elegant branch of mathematics with applications in several areas of computer Electronic supplementary material The online version of this article (https://doi.org/10.1007/s0045 3-020-00695-6) contains supplementary material, which is available to authorized users. * Yuichi Nagata [email protected]‑u.ac.jp 1
Graduate School of Technology, Industrial and Social Sciences, Tokushima University, 2‑1 Minami‑jousanjima, Tokushima‑shi, Tokushima 770‑8506, Japan
2
Department of Information and System Engineering, Faculty of Science and Engineering, Chuo University, Bunkyo‑ku, Tokyo 112‑8551, Japan
13
Vol.:(0123456789)
Algorithmica
science. The Dutch artist M. C. Escher studied tiling from a mathematical perspective and created many artistic tilings, each of which consists of one or a few recognizable figures, such as animals. Such artistic tiling is now called Escher tiling. People have actively designed new Escher-like tilings because it is a highly intellectual task to design artistic figures while satisfying the required constraints to realize tiling. Several illustration software packages have been proposed to support the creation process of Escher-like tiling. Unlike conventional support systems for Escher-like tilings, Kaplan and Salesin [7] developed a method to automatically generate Escher-like tilings. They first formulated an optimization problem called the Escherization problem, which is defined as follows: Given a closed plane figure S (goal figure), find a closed figure T such that 1. T is as close as possible to S, and 2. copies of T fit togeth
Data Loading...
