Rectangle Transformation Problem

doi:10.1007/s00453-019-00563-y

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	Rectangle Transformation Problem
	He, Kun 2,3; Wang, Shaojiang 3,4; Xia, Mingji 3,4; Pan, Yicheng 1
刊名	ALGORITHMICA
	2019-07-01
卷号	81 期号:7 页码:2876-2898
关键词	Rectangle transformation problem (RTP) Strict RTP Rectangle tiling pattern Smith diagram Upper and lower bounds
ISSN号	0178-4617
DOI	10.1007/s00453-019-00563-y
英文摘要	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.
资助项目	National Science Foundation for Young Scientists of China[61807034] ; National Natural Science Foundation of China[61433014]
WOS研究方向	Computer Science ; Mathematics
语种	英语
出版者	SPRINGER
WOS记录号	WOS:000467379400009
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/4235]
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Pan, Yicheng
作者单位	1.Beihang Univ, State Key Lab Software Dev Environm, Beijing, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, Beijing, Peoples R China 3.Univ Chinese Acad Sci, Beijing, Peoples R China 4.Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China
推荐引用方式 GB/T 7714	He, Kun,Wang, Shaojiang,Xia, Mingji,et al. Rectangle Transformation Problem[J]. ALGORITHMICA,2019,81(7):2876-2898.
APA	He, Kun,Wang, Shaojiang,Xia, Mingji,&Pan, Yicheng.(2019).Rectangle Transformation Problem.ALGORITHMICA,81(7),2876-2898.
MLA	He, Kun,et al."Rectangle Transformation Problem".ALGORITHMICA 81.7(2019):2876-2898.