跳到主要內容

臺灣博碩士論文加值系統

(44.201.99.222) 您好!臺灣時間:2022/12/04 00:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林鈞仁
研究生(外文):Chun-Jen Lin
論文名稱(外文):A Study on the Minimum Area of Rectilinear Polygons Realized by Turn Sequences
指導教授:何錦文高明達高明達引用關係
指導教授(外文):Chin-Wen HoMing-Tat Ko
學位類別:碩士
校院名稱:國立中央大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:49
中文關鍵詞:直角多邊形頂點角度序列最小面積凸多邊形
外文關鍵詞:rectilinear polygonturn sequenceminimum areamonotone
相關次數:
  • 被引用被引用:0
  • 點閱點閱:125
  • 評分評分:
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
在本論文中,我們考慮以其頂點角度之序列,來重建最小面積直角多邊形的問題。我們提出以下兩個結果:
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.
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)
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top