PANGFENG LIU2009-05-062018-07-052009-05-062018-07-05200500200190http://ntur.lib.ntu.edu.tw//handle/246246/155126https://www.scopus.com/inward/record.uri?eid=2-s2.0-26444476050&doi=10.1016%2fj.ipl.2005.07.002&partnerID=40&md5=489018e24b8ceb2ed941a743cd1727efThis 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.application/pdf155522 bytesapplication/pdfen-USDesign of algorithms; Mesh generation; Min-max degree triangulation; Rectangle and convex polygonsAlgorithms; Boundary conditions; Optimization; Design of algorithms; Mesh generation; Min-max degree triangulation; Rectangle and convex polygons; Triangulationjournal article10.1016/j.ipl.2005.07.0022-s2.0-26444476050http://ntur.lib.ntu.edu.tw/bitstream/246246/155126/1/06.pdf