From:jeffe@duke.cs.duke.eduSubject:The last mesh generation problemTo:David Eppstein <eppstein@ICS.UCI.EDU>Date:Thu, 10 Apr 1997 18:53:13 -0400 (EDT)

David -- I just found your list of problems for your mesh generation class. Stuff is known about optimal convex decompositions of simple polygons. If Steiner points are not allowed, an algorithm of Keil runs in time O(r^2 n log n). If Steiner points are allowed, an algorithm of Chazelle -- from his PhD thesis -- runs in time O(n + r^3). As you guessed, both are dynamic programming algorithms. Sounds like a fun seminar. -- Jeff @article{k-dpsc-85 , author = "J. M. Keil" , title = "Decomposing a polygon into simpler components" , journal = "SIAM J. Comput." , volume = 14 , year = 1985 , pages = "799--817" , keywords = "dynamic programming, convex, polygons, star-shaped, partition, decomposition" } @incollection{ks-mdpo-85 , author = "J. M. Keil and J.-R. Sack" , title = "Minimum decompositions of polygonal objects" , editor = "G. T. Toussaint" , booktitle = "Computational Geometry" , publisher = "North-Holland" , address = "Amsterdam, Netherlands" , year = 1985 , pages = "197--216" , keywords = "survey paper, convex, polygons, star-shaped, partition, decomposition, covering" } @incollection{cd-ocd-85 , author = "B. Chazelle and D. P. Dobkin" , title = "Optimal convex decompositions" , editor = "G. T. Toussaint" , booktitle = "Computational Geometry" , publisher = "North-Holland" , address = "Amsterdam, Netherlands" , year = 1985 , pages = "63--133" , succeeds = "cd-dpicp-79" }