中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Rectangle Transformation Problem

文献类型：期刊论文

作者He, Kun2,3; Wang, Shaojiang3,4; Xia, Mingji3,4; Pan, Yicheng1
刊名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
DOI10.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
语种英语
WOS记录号WOS:000467379400009
出版者SPRINGER
源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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。