Rectangle transformation problem

DOI10.1007/S00453-019-00563-YMaRDI QIDQ2415366zbMATH OpenOpenAlexWikidataFDO

Authors Shao-Jiang Wang, Kun He, Yicheng Pan, Mingji Xia

Publication date 21 May 2019

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsupper boundsrectangle tiling patternrectangle transformation problem (RTP)Smith diagramstrict RTP

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: In this paper, we propose the rectangle transformation problem (RTP) and its variants. RTP asks for a transformation by a rectangle partition between two rectangles of the same area. We are interested in the minimum RTP which requires to minimize the partition size. We mainly focus on the strict rectangle transformation problem (SRTP) in which rotation is not allowed in transforming. We show that SRTP has no finite solution if the ratio of the two parallel side lengths of input rectangles is irrational. So we turn to its complement denoted by SIRTP, in which case all side lengths can be assumed integral. We give a polynomial time algorithm ALGSIRTP which gives a solution at most $q/p+O(sqrtp)$ to SIRTP$(p,q)$ ($qgeqp$), where $p$ and $q$ are two integer side lengths of input rectangles $pimesq$ and $qimesp$, and so ALGSIRTP is a $O(sqrtp)$-approximation algorithm for minimum SIRTP$(p,q)$. On the other hand, we show that there is not constant solution to SIRTP$(p,q)$ for all integers $p$ and $q$ ($q>p$) even though the ratio $q/p$ is within any constant range. We also raise a series of open questions for the research along this line.

Recommendations

• An approximation algorithm for dissecting a rectangle into rectangles with specified areas
• Algorithms and Computation
• A fast algorithm for cutting a rectangle into equal rectangular pieces
• Partitioning a square into rectangles: NP-Completeness and approximation algorithms
• Improved bounds for rectangular and guillotine partitions

Cites work

• scientific article; zbMATH DE number 1424299 (Why is no real title available?)
• A LINEAR-TIME ALGORITHM FOR COVERING SIMPLE POLYGONS WITH SIMILAR RECTANGLES
• Conjecture and proof
• Covering Polygons Is Hard
• Dissection with the fewest pieces is hard, even to approximate
• Fourteen Proofs of a Result About Tiling a Rectangle
• Graph-Theoretic Solutions to Computational Geometry Problems
• Minimum-weight triangulation is NP-hard
• Partitioning a rectangle into small perimeter rectangles
• Recent advances on two-dimensional bin packing problems
• Rectangles as sums of squares
• Tiling a rectangle with the fewest squares

This page was built for publication: Rectangle transformation problem

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