https://scholars.lib.ntu.edu.tw/handle/123456789/118315
標題: | Minimum degree triangulation for rectangular domains | 作者: | PANGFENG LIU | 關鍵字: | Design of algorithms; Mesh generation; Min-max degree triangulation; Rectangle and convex polygons | 公開日期: | 2005 | 卷: | 96 | 期: | 4 | 起(迄)頁: | 128-135 | 來源出版物: | Information Processing Letters | 摘要: | This paper describes an optimal triangulation algorithm for rectangles. We derive lower bounds on the maximum degree of triangulation, and show that our triangulation algorithm matches the lower bounds. Several important observations are also made, including a zig-zag condition that can verify whether a triangulation can minimizes the maximum degree to 4 or not. In addition, this paper identifies the necessary and sufficient condition that there exists a maximum degree 4 triangulation for convex polygons, and gives a linear time checking algorithm. © 2005 Elsevier B.V. All rights reserved. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/155126 https://www.scopus.com/inward/record.uri?eid=2-s2.0-26444476050&doi=10.1016%2fj.ipl.2005.07.002&partnerID=40&md5=489018e24b8ceb2ed941a743cd1727ef |
ISSN: | 00200190 | DOI: | 10.1016/j.ipl.2005.07.002 | SDG/關鍵字: | Algorithms; Boundary conditions; Optimization; Design of algorithms; Mesh generation; Min-max degree triangulation; Rectangle and convex polygons; Triangulation |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。