An efficient exhaustive search algorithm for the Escherization problem

DOI10.1007/S00453-020-00695-6zbMATH Open1456.52024arXiv1912.09605OpenAlexW3013660948MaRDI QIDQ2196607FDOQ2196607

Shinji Imahori, Yuichi Nagata

Publication date: 3 September 2020

Published in: Algorithmica (Search for Journal in Brave)

Abstract: In the Escherization problem, given a closed figure in a plane, the objective is to find a closed figure that is as close as possible to the input figure and tiles the plane. Koizumi and Sugihara's formulation reduces this problem to an eigenvalue problem in which the tile and input figures are represented as $n$-point polygons. In their formulation, the same number of points are assigned to every tiling edge, which forms a tiling template, to parameterize the tile shape. By considering all possible configurations for the assignment of the $n$ points to the tiling edges, we can achieve much flexibility in terms of the possible tile shapes and the quality of the optimal tile shape improves drastically, at the cost of enormous computational effort. In this paper, we propose an efficient algorithm to find the optimal tile shape for this extended formulation of the Escherization problem.

Full work available at URL: https://arxiv.org/abs/1912.09605

Recommendations

• Maximum eigenvalue problem for Escherization
• Escher-like tilings with weights
• scientific article; zbMATH DE number 1735725
• Computational aspects of M. C. Escher's ribbon patterns
• Escher's combinatorial patterns

zbMATH Keywords

tessellationEscherizationisohedral tilingEscher-like tilingprocrustes distance

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Cites Work

• Numerical Methods for Large Eigenvalue Problems
• Title not available (Why is that?)
• Maximum eigenvalue problem for Escherization
• Escher-like Tilings with Weights
• Introductory Tiling Theory for Computer Graphics

Cited In (1)

• A finite exact algorithm for epsilon-core membership in two dimensions

This page was built for publication: An efficient exhaustive search algorithm for the Escherization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196607)