Rectangle transformation problem

DOI10.1007/S00453-019-00563-YzbMATH Open1421.68178arXiv1710.10924OpenAlexW2962933775WikidataQ128129169 ScholiaQ128129169MaRDI QIDQ2415366FDOQ2415366

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

Publication date: 21 May 2019

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Minimum-weight triangulation is NP-hard
• Recent advances on two-dimensional bin packing problems
• Covering Polygons Is Hard
• Fourteen Proofs of a Result About Tiling a Rectangle
• Title not available (Why is that?)
• Tiling a rectangle with the fewest squares
• Rectangles as sums of squares
• Partitioning a rectangle into small perimeter rectangles
• A LINEAR-TIME ALGORITHM FOR COVERING SIMPLE POLYGONS WITH SIMILAR RECTANGLES
• Graph-Theoretic Solutions to Computational Geometry Problems
• Conjecture and proof
• Dissection with the Fewest Pieces is Hard, Even to Approximate

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)