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

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

林鈞仁(Chun-Jen Lin)

指導教授 ： 何錦文 ； 高明達

國立中央大學/資訊電機學院/資訊工程學系/碩士(2015年)

摘要

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

參考文獻

Extension of All Edges Incident to Re

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