網格式曼哈頓塔與單層網格式多面體之沿邊展開

Edge-Unfolding Lattice Manhattan Towers and One-Layer Lattice Polyhedra

魏煜杰(Yu-Jie Wei)

指導教授 ： 潘雙洪

國立清華大學/電機資訊學院/資訊工程學系/碩士(2011年)

摘要

長久以來，辨識非凸多面體是否存在展開演算法是一個尚未解決的問題。在近年的研究中，專注於非凸多面體中的一類─「正交多面體」的展開，並提出了grid-edge以及grid-vertex展開演算法。然而有兩個前提，最後的面要再切割為n_1*n_2的方格且只能對虧格為零的正交多面體做展開。
所以在此篇論文中，我們使用了由單位立方體結合而成的網格式多面體取代原先的正交多面體，並對此圖形設計展開演算法。研究中的第一個主題是考慮網格式曼哈頓塔的邊展開演算法。主要的想法是利用帶狀的長條去攤平每一層上的表面，而且這些長條也被用做連接不同層的橋接器。第二個主題則是考慮含有形似單位立方體的洞，此類單層網格式多面體之邊展開演算法。主要的概念是找出一條路徑將所有的洞連結在一起，並讓最後展開的結果維持向右及向上延伸。在此論文中，我們提出了不需重新對表面切割的邊展開，也證明了虧格不為零的單層網格式多面體存在邊展開演算法。

關鍵字

邊展開 ； 網格式多面體

並列摘要

It is a long-standing open problem to recognize whether every nonconvex polyhedron has a general unfolding algorithm. In the recent research, it is proposed grid-edge and grid-vertex unfolding algorithms to solve orthogonal polyhedron which is one class of nonconvex polyhedra. Since there are two fundamentals, the separated surface must have a refinement to be divided into n_1*n_2 grid and the orthogonal polyhedron is genus-zero.

The aim of this thesis is to consider the unfolding algorithms run on the lattice polyhedra formed by unit cubes. The first research topic is the edge-unfolding algorithm for lattice Manhattan Towers. The main idea is to use many strips to flatten the faces of each layer and these strips are regarded as the bridge between two bands. The second research is to consider the edge-unfolding algorithm for one-layer lattice polyhedra with cubic holes. The principal concept is finding the connected bridge to link the holes and let the extending direction keep in rightward or upward direction. We propose the algorithms which are 1*1 edge-unfolding without refining grid size. It is also shown that there exists unfolding methods to flatten one-layer lattice polyhedra with genus >1 and monotone boundary.

並列關鍵字

edge-unfolding ； lattice polyhedra

參考文獻

Tehno-Teoreticheskoi Literaturu, 1950. In Russian. See [2] for English translation.

[5] Boris Aronov and Joseph O'Rourke. Nonoverlap of the star unfolding. Discrete &

Computational Geometry, 8:219-250, 1992.

[8] Mirela Damian, Robin Y. Flatland, and Joseph O'Rourke. Epsilon-unfolding orthogonal polyhedra. Graphs and Combinatorics, 23(Suppl):179-194, 2006.

thogonal polyhedra. Discrete & Computational Geometry, 39(1-3):213-238, 2008.