博碩士論文 101522019 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:14 、訪客IP:3.236.118.225
姓名 林鈞仁(Chun-Jen Lin)  查詢紙本館藏   畢業系所 資訊工程學系
論文名稱
(A Study on the Minimum Area of Rectilinear Polygons Realized by Turn Sequences)
相關論文
★ 一種減輕LEO衛星網路干擾的方案★ 捷徑問題在特殊圖形上之演算研究
★ 行動電腦教室與其管理系統的設計與建置★ 蛋白質體視覺化系統之實作
★ 最小切割樹群聚演算法極端情形之研究★ 教室內應用無線科技之一對一數位學習模式
★ 蛋白質交互作用網路之視覺化系統★ 以賓果式遊戲輔助技巧熟練之數位學習環境設計與實作
★ 蛋白質註解的三維視覺化工具★ Joyce 2:一個在一對一數位教室環境下之小組競爭遊戲
★ 同儕計算網路上內文散佈演算法之實作與效能評估★ 在直角多邊形上使用基因演算法畫樹之研究
★ 經由潛在語義的線索從蛋白質交互作用網路進行蛋白質功能的預測★ 從生物文件中萃取出蛋白質或基因之名稱
★ 利用蛋白質交互作用網路偵測必要性蛋白質★ 族群基因繪圖演算法的改良
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 在本論文中,我們考慮以其頂點角度之序列,來重建最小面積直角多邊形的問題。我們提出以下兩個結果:

1. 研究n 點的最小面積直角多邊形的性質,並以此性質將之分為四類,以及算出其中三類多邊形的個數。

2. 給定一直角凸多邊形之角度序列S,我們提出一計算其最小面積之公式。
摘要(英) In this thesis, we consider the problem of reconstructing rectilinear polygons with minimum area, from a sequence of angles of vertices.

We provide two results:



1. Studying properties of n-vertex rectilinear polygons with minimum area, classifying those polygons into four types by these properties, and computing the number of polygons in each of three of them.



2. Given a sequence S of angles of a monotone rectilinear polygon, we propose a formula to compute the minimum of area of monotone rectilinear polygons with turn sequence S.
關鍵字(中) ★ 直角多邊形
★ 頂點角度序列
★ 最小面積
★ 凸多邊形
關鍵字(英) ★ rectilinear polygon
★ turn sequence
★ minimum area
★ monotone
論文目次 1 Introduction 1

2 Preliminaries 3

2.1 Formulas to Compute (n) and Δ(n) . . . . . . . . . . . . . . . . . . . . . 3

2.2 Pick′s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.3 Canonical Pockets of Rectilinear Polygons . . . . . . . . . . . . . . . . . . 4

2.4 Introduction of Monotonicity . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Realizations of Polygons with Area (n) 6

3.1 The Patterns of Polygons of Type I . . . . . . . . . . . . . . . . . . . . . . 6

3.2 The Patterns of Polygons of Type II.1 . . . . . . . . . . . . . . . . . . . . 9

3.3 The Patterns of Polygons of Type II.2 . . . . . . . . . . . . . . . . . . . . 11

3.4 The Patterns of Polygons of Type II.3 . . . . . . . . . . . . . . . . . . . . 14

4 Minimum Area of Monotone Polygons with a Given Turn Sequence 18

4.1 The Area of P(S) with One Stair and Two Adjacent Stairs . . . . . . . . . 19

4.2 The Area of P(S) with Two Opposite Stairs . . . . . . . . . . . . . . . . . 21

4.3 The Area of P(S) with Three Stairs . . . . . . . . . . . . . . . . . . . . . . 27

4.4 The Area of P(S) with Four Stairs . . . . . . . . . . . . . . . . . . . . . . . 32

5 Conclusion Remarks 40

Reference 41
參考文獻 [1] Bajuelos, A.L., Tomas, A.P., Marques, F.: Partitioning Orthogonal Polygons by

Extension of All Edges Incident to Re

ex Vertices: Lower and Upper Bounds on

the Number of Pieces. In: Lagana, A., Gavrilova, M.L., Kumar, V., Mun, Y., Tan,

C.J.K., Gervasi, O. (eds.) ICCSA 2004. LNCS, vol. 3045, pp. 127-136. Springer,

Heidelberg (2004)

[2] Biedl, T., Durocher, S., Snoeyink, J.: Reconstructing polygons from scanner data.

Theoretical Computer Science 412, 4161-4172 (2011)

[3] Chen, D.Z., Wang, H.: An improved algorithm for reconstructing a simple polygon

from its visibility angles. Computational Geometry: Theory and Applications 45,

254-257 (2012)

[4] Disser, Y., Mihalak, M., Widmayer, P.: Reconstructing a simple polygon from its

angles. Computational Geometry: Theory and Applications 44, 418-426 (2011)

[5] O′Rourke, J.: An alternate proof of the rectilinear art gallery theorem. Journal of

Geometry 21, 118-130 (1983)

[6] O′Rourke, J.: Uniqueness of orthogonal connect-the-dots. In: Toussaint, G.T. (ed.)

Computational Morphology, pp. 97-104 (1988)

[7] Pick, Georg.: Geometrisches zur Zahlenlehre". Sitzungsberichte des deutschen

naturwissenschaftlich-medicinischen Vereines fur Bohmen Lotos" in Prag. (Neue

Folge) 19: 311-319 (1899)

[8] Sang Won Bae, Yoshio Okamoto, and Chan-Su Shin: Area bounds of rectilinear

polygons realized by angle sequences. Proceedings of 23rd International Symposium

on Algorithms and Computation (ISAAC 2012), Lecture Notes in Computer Science

7676 (2012)
指導教授 何錦文、高明達(Chin-Wen Ho Ming-Tat Ko) 審核日期 2015-8-31
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明