A Study on the Minimum Area of Rectilinear Polygons Realized by Turn Sequences

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：11

、訪客IP：18.191.54.249

姓名

林鈞仁(Chun-Jen Lin) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(A Study on the Minimum Area of Rectilinear Polygons Realized by Turn Sequences)

相關論文

★ 一種減輕LEO衛星網路干擾的方案	★ 萃取駕駛人在不同環境之駕駛行為方法
★ 非地面網路中基於位置的隨機接入分配方法	★ TrustFADE: 針對可程式化邏輯區塊之安全認證方法
★ 捷徑問題在特殊圖形上之演算研究	★ 行動電腦教室與其管理系統的設計與建置
★ 蛋白質體視覺化系統之實作	★ 最小切割樹群聚演算法極端情形之研究
★ 教室內應用無線科技之一對一數位學習模式	★ 蛋白質交互作用網路之視覺化系統
★ 以賓果式遊戲輔助技巧熟練之數位學習環境設計與實作	★ 蛋白質註解的三維視覺化工具
★ Joyce 2：一個在一對一數位教室環境下之小組競爭遊戲	★ 同儕計算網路上內文散佈演算法之實作與效能評估
★ 在直角多邊形上使用基因演算法畫樹之研究	★ 經由潛在語義的線索從蛋白質交互作用網路進行蛋白質功能的預測

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

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

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

推文