WEKO3
インデックスリンク
アイテム
A Compact Encoding of Rectangular Drawings with Edge Lengths
https://iwate-u.repo.nii.ac.jp/records/10347
https://iwate-u.repo.nii.ac.jp/records/1034720b02faa-0700-4d63-9edf-6d5eeab2e871
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
ieicet-ve96-an6p1032-1035.pdf (376.1 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-09-25 | |||||||||
| タイトル | ||||||||||
| タイトル | A Compact Encoding of Rectangular Drawings with Edge Lengths | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | graph | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | algorithm | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | encoding | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | rectangular drawing | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | grid rectangular drawing | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | journal article | |||||||||
| 著者 |
NAKANO, Shin-ichi
× NAKANO, Shin-ichi
× YAMANAKA, Katsuhisa
|
|||||||||
| 著者(機関) | ||||||||||
| 値 | Department of Computer Science, Gunma University | |||||||||
| 著者(機関) | ||||||||||
| 値 | Department of Electrical Engineering and Computer Science, Iwate University | |||||||||
| 登録日 | ||||||||||
| 日付 | 2014-09-25 | |||||||||
| 書誌情報 |
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 巻 E96-A, 号 6, p. 1032-1035, 発行日 2013-06-01 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 0916-8508 | |||||||||
| Abstract | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | A rectangular drawing is a plane drawing of a graph in which every face is a rectangle. Rectangular drawings have an application for floorplans, which may have a huge number of faces, so compact code to store the drawings is desired. The most compact code for rectangular drawings needs at most 4f-4 bits, where f is the number of inner faces of the drawing. The code stores only the graph structure of rectangular drawings, so the length of each edge is not encoded. A grid rectangular drawing is a rectangular drawing in which each vertex has integer coordinates. To store grid rectangular drawings, we need to store some information for lengths or coordinates. One can store a grid rectangular drawing by the code for rectangular drawings and the width and height of each inner face. Such a code needs 4f-4 + f⌈log W⌉ + f⌈log H⌉ + o(f) + o(W) + o(H) bits*, where W and H are the maximum width and the maximum height of inner faces, respectively. In this paper we design a simple and compact code for grid rectangular drawings. The code needs 4f-4 + (f+1)⌈log L⌉ + o(f) + o(L) bits for each grid rectangular drawing, where L is the maximum length of edges in the drawing. Note that L ≤ max{W,H} holds. Our encoding and decoding algorithms run in O(f) time. | |||||||||
| 出版者 | ||||||||||
| 出版者 | The Institute of Electronics, Information and Communication Engineers | |||||||||
| 権利 | ||||||||||
| 権利情報 | Copyright (c) 2013 The Institute of Electronics, Information and Communication Engineers | |||||||||
| DOI | ||||||||||
| 関連タイプ | isIdenticalTo | |||||||||
| 識別子タイプ | DOI | |||||||||
| 関連識別子 | 10.1587/transfun.E96.A.1032 | |||||||||
| 著者版フラグ | ||||||||||
| 出版タイプ | VoR | |||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||
