The search functionality is under construction.

Author Search Result

[Author] Md. Saidur RAHMAN(1hit)

1-1hit
  • Enumerating Floorplans with Columns

    Katsuhisa YAMANAKA  Md. Saidur RAHMAN  Shin-ichi NAKANO  

     
    PAPER

      Vol:
    E101-A No:9
      Page(s):
    1392-1397

    Given an axis-aligned rectangle R and a set P of n points in the proper inside of R we wish to partition R into a set S of n+1 rectangles so that each point in P is on the common boundary between two rectangles in S. We call such a partition of R a feasible floorplan of R with respect to P. Intuitively, P is the locations of columns and a feasible floorplan is a floorplan in which no column is in the proper inside of a room, i.e., columns are allowed to be placed only on the partition walls between rooms. In this paper we give an efficient algorithm to enumerate all feasible floorplans of R with respect to P. The algorithm is based on the reverse search method, and enumerates all feasible floorplans in O(|SP|) time using O(n) space, where SP is the set of the feasible floorplans of R with respect to P, while the known algorithms need either O(n|SP|) time and O(n) space or O(log n|SP|) time and O(n3) space.