Rectangle Transformation Problem

doi:10.1007/s00453-019-00563-y

	Rectangle Transformation Problem
	Wang, Shaojiang 1,2; He, Kun 2,3; Pan, Yicheng 4; Xia, Mingji 1,2
	2019-07-01
发表期刊	ALGORITHMICA
ISSN	0178-4617
卷号	81 期号:7 页码:2876-2898
摘要	In this paper, we propose the rectangle transformation problem (RTP) and its variants. RTP asks for rectangle partitions on two rectangles of the same area which produce two identical sets of pieces. We are interested in the minimum RTP which requires to minimize the partition size. This initiates the algorithmic study of dissection problems in module number optimization, particularly in the category of rectangle partition. We mainly focus on the strict rectangle transformation problem (SRTP) in which rotation is not allowed during the transformation. It has been shown 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 complemental case, SRTP with integral input, denoted by SIRTP, in which case both side lengths are assumed integral. We give a polynomial time algorithm ALGSIRTP which gives a solution at most q/p+7log2p to SIRTP(p,q) (qp), where p and q are two integral side lengths of input rectangles pxq and qxp. Note that q/p is an intrinsic lower bound for SIRTP(p,q). So ALGSIRTP is a (7logp)-approximation algorithm for minimum SIRTP(p,q). On the other hand, we show that for any epsilon>0 and any constant range (1,1+), there are integers p and q (q>p) of ratio q/p in this range, such that there is no solution less than max{q/p,log21-epsilon q} to SIRTP(p,q). This is an almost tight bound since the algorithm ALGSIRTP gives an upper bound 7log2p+O(1) in this case. We also raise a long series of open questions for further research along this line.
关键词	Rectangle transformation problem (RTP) Strict RTP Rectangle tiling pattern Smith diagram Upper and lower bounds
DOI	10.1007/s00453-019-00563-y
收录类别	SCI
语种	英语
资助项目	National Science Foundation for Young Scientists of China[61807034] ; National Natural Science Foundation of China[61433014]
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Software Engineering ; Mathematics, Applied
WOS记录号	WOS:000467379400009
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/4236
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Pan, Yicheng
作者单位	1.Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China 2.Univ Chinese Acad Sci, Beijing, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, Beijing, Peoples R China 4.Beihang Univ, State Key Lab Software Dev Environm, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Wang, Shaojiang,He, Kun,Pan, Yicheng,et al. Rectangle Transformation Problem[J]. ALGORITHMICA,2019,81(7):2876-2898.
APA	Wang, Shaojiang,He, Kun,Pan, Yicheng,&Xia, Mingji.(2019).Rectangle Transformation Problem.ALGORITHMICA,81(7),2876-2898.
MLA	Wang, Shaojiang,et al."Rectangle Transformation Problem".ALGORITHMICA 81.7(2019):2876-2898.