請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40621
標題: | 矩形繪圖緊密編碼法之改良 Improved Compact Encoding of Rectangular Drawings |
作者: | Po-Ying Chuang 莊柏穎 |
指導教授: | 呂學一(Hsueh-I Lu) |
關鍵字: | 矩形,繪圖,編碼,壓縮,簡短, rectangular,drawings,encoding,compression,succinct, |
出版年 : | 2008 |
學位: | 碩士 |
摘要: | 一個平面圖的矩形繪圖是點為圓點、邊為鉛垂或是水平線,而且各區域均為矩形之繪圖。一個擁有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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40621 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 660.84 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。