矩形繪圖緊密編碼法之改良

Improved Compact Encoding of Rectangular Drawings

莊柏穎(Po-Ying Chuang)

指導教授 ： 呂學一

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.02171

摘要

一個平面圖的矩形繪圖是點為圓點、邊為鉛垂或是水平線，而且各區域均為矩形之繪圖。一個擁有m條邊的矩型繪圖，先前已知最好的緊密編碼法為Yamanaka與Nakano所提出，且需要至多5m/3個位元來記錄。他們的緊密編碼法之編碼與解碼，均可以在O(m)的時間內完成。我們將所需要的位元數目改良到至多1.53m+10.83個位元，而沒有增加編碼與解碼所需要花費的時間。

關鍵字

矩形 ； 繪圖 ； 編碼 ； 壓縮 ； 簡短

並列摘要

A rectangular drawing of a plane graph is a drawing whose nodes are points, edges are vertical or horizontal lines, and regions are all rectangles. The best previously known compact representation of an m-edge rectangular drawing, due to Yamanaka and Nakano, requires at most 5m/3 bits. The encoding and decoding of their compact representation can both be done in O(m) time. We improve the required number of bits to at most 1.53m+10.83 without increasing the time required for encoding and decoding.

並列關鍵字

rectangular ； drawings ； encoding ； compression ； succinct

參考文獻

[1] H. H. Chan, S. N. Adya, and I. L. Markov. Are floorplan representations important in

pages 129-136, 2005.

[2] D. Chigira and S.-I. Nakano. Constant time generation of rectangular drawings with

exactly n faces including at most k store rooms. IEICE Transactions on Fundamentals of

130, 2007.