An Upper Bound on the Number of Rectangulations of a Point Set

摘要：

We consider the number of different ways to divide a rectangle containing n noncorectilinear points into smaller rectangles by n non-intersecting axis-parallel segments, such that every point is on a segment. Using a novel counting technique of Santos and Seidel 12, we show an upper bound of O(20n/n4) on this number.

作者: Eyal Ackerman Gill Barequet Ron Y. Pinter

作者单位: Dept. of Computer Science Technion-Israel Institute of Technology, Haifa 32000, Israel

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 554-559

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）