2019/12/20 by Yuichi Nagata, Shinji Imahori
Computer Science · Engineering · Mathematics · #3D Shape Modeling and Analysis #Algorithm #Artificial intelligence #Computational geometry #Computer science #Eigenvalues and eigenvectors #Enhanced Data Rates for GSM Evolution #Flexibility (engineering) #Geometry #Image Processing and 3D Reconstruction #Interior point method #Manufacturing Process and Optimization #Mathematical optimization #Mathematics #Plane (geometry) #Point (geometry) #Theory of computation #Tile #cs.CG #cs.DS
paper · pdf · doi:10.1007/s00453-020-00695-6
published as Algorithmica 82, 2502-2534 (2020) · This version has been submitted to an international journal
arxiv created 2019/12/20 · openalex publication_date 2020/03/23 · openalex created_date 2020/04/03 · arxiv updated 2020/11/23 · openalex updated_date 2026/08/05
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.