A floorplan is a partition of an axis-aligned rectangle into a set of smaller rectangles. Given an axis-aligned rectangle R and a set P of points in R we wish to partition R into a set S of rectangles so that each point in P is on the boundary of rectangles in S. We call such a partition of R a floorplan covering P. Intuitively P is the locations of columns and a floorplan covering P is a floorplan in which no column is in the proper inside of a room. If no two points in P have the same x-coordinate and no two points in P have the same y-coordinate, then one can generate all floorplans covering P in O(|P|) time for each. In this paper we design an algorithm to generate all floorplans covering P, when P is any set of points, which is more practical setting in architecture. The running time of the algorithm is O(|P|) time for each.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Enumerating Floorplans with Any Set of Columns

  • Yosuke Kikuchi,
  • Shin-ichi Nakano

摘要

A floorplan is a partition of an axis-aligned rectangle into a set of smaller rectangles. Given an axis-aligned rectangle R and a set P of points in R we wish to partition R into a set S of rectangles so that each point in P is on the boundary of rectangles in S. We call such a partition of R a floorplan covering P. Intuitively P is the locations of columns and a floorplan covering P is a floorplan in which no column is in the proper inside of a room. If no two points in P have the same x-coordinate and no two points in P have the same y-coordinate, then one can generate all floorplans covering P in O(|P|) time for each. In this paper we design an algorithm to generate all floorplans covering P, when P is any set of points, which is more practical setting in architecture. The running time of the algorithm is O(|P|) time for each.