Another Optimal Binary Representation of Mosaic Floorplans

Katsuhisa YAMANAKA  Shin-ichi NAKANO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.6   pp.1223-1224
Publication Date: 2015/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.1223
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
algorithm,  coding,  decoding,  floorplan,  mosaic floorplan,  

Full Text: PDF(136.5KB)
>>Buy this Article


Summary: 
Recently a compact code of mosaic floorplans with ƒ inner face was proposed by He. The length of the code is 3ƒ-3 bits and asymptotically optimal. In this paper, we propose a new code of mosaic floorplans with ƒ inner faces including k boundary faces. The length of our code is at most $3f - rac{k}{2} - 1$ bits. Hence our code is shorter than or equal to the code by He, except for few small floorplans with k=ƒ≤3. Coding and decoding can be done in O(ƒ) time.