呂學一Lu, Hsueh-I臺灣大學:資訊工程學研究所莊柏穎Chuang, Po-YingPo-YingChuang2010-05-182018-07-052010-05-182018-07-052008U0001-2507200821305400http://ntur.lib.ntu.edu.tw//handle/246246/183607一個平面圖的矩形繪圖是點為圓點、邊為鉛垂或是水平線，而且各區域均為矩形之繪圖。一個擁有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.Acknowledgements ihinese Abstract iinglish Abstract iiiontents ivist of Figures vi Introduction 1 Our encoding 4.1 V-links and h-links . . . . . . . . . 4.2 Face types . . . . . . . . . . . . . 6.3 The encoding string . . . . . . . . . 6.4 Measuring the encoding string . . . . 7 Correctness of our encoding 9.1 Lemmas for face adjacencies . . . . . 9.2 Reconstructions of v-links and h-links . . . . . 11.3 Proving Theorem 1.1 . . . . . . . . . 14 Conclusions 15ibliography 16application/pdf676700 bytesapplication/pdfen-US矩形繪圖編碼壓縮簡短rectangulardrawingsencodingcompressionsuccinctthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/183607/1/ntu-97-R95922056-1.pdf