L字形描画のコンパクトな符号

概要

論文の詳細を見る
A floorplan is a partition of a rectangle into a set of rectilinear polygons. An L-floorplan is a floorplan where each rectilinear polygon is either a rectangle or an L-shape polygon. Floorplans have many important applications including VLSI layout. Since the size of floorplans may be huge, compact encodings of floorplans are desired. Several compact encodings of floorplans are known where each rectilinear polygon is a rectangle only. In this paper we design two compact encodings for L-floorplans with 6f + 3L + 2n_2 - 2 and 5f + 6L - 4 bits, respectively, where f is the number of polygons, L is the number of L-shape polygons and n_2 is the number of vertices with degree 2. The encoding techniques are simple and both encoding and decoding can be performed in O(f) = O(n) time.
一般社団法人電子情報通信学会の論文
2012-05-07