The quarter-state-sequence floorplan representation

A floorplan of a bounding box is its dissection into rectangles (rooms) by horizontal and vertical segments. This paper proposes a string data structure called the Quarter-state sequence (or Q sequence) to represent the floorplan. The Q sequence is a concatenation of the states of rooms along the Ab...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on circuits and systems. 1, Fundamental theory and applications Fundamental theory and applications, 2003-03, Vol.50 (3), p.376-386
Main Authors: Sakanushi, K., Kajitani, Y., Mehta, D.P.
Format: Article
Language:English
Subjects:
Combinatorial mathematics
Cost function
Data structures
Decoding
Graph theory
Hip
Large scale integration
Simulated annealing
Tree graphs
Very large scale integration
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A floorplan of a bounding box is its dissection into rectangles (rooms) by horizontal and vertical segments. This paper proposes a string data structure called the Quarter-state sequence (or Q sequence) to represent the floorplan. The Q sequence is a concatenation of the states of rooms along the Abe order and is related to the VH graph, which is the union of the vertical-constraint and horizontal-constraint graphs. It is proved that any floorplan of n rooms is uniquely encoded by a Q sequence and any Q sequence is uniquely decoded to a floorplan, both in O(n) time. An exact formula for counting distinct floorplans is given and compared with existing bounds. A linear time transformation of one Q sequence to another is defined. An n-room packing algorithm based on simulated annealing was implemented and found to compare favorably with existing packing algorithms.
ISSN:1057-7122
1558-1268
DOI:10.1109/TCSI.2003.809442