From: Sebastien Loisel Newsgroups: comp.graphics.algorithms Subject: Re: Concave -> Convex algorithms? Date: Sun, 25 Feb 1996 19:56:53 -0800 Eric A. Drumbor wrote: > > Subject says it all. I'm looking for an algorithm or even the theory > behind converting a concave polygon into a 'least number' set of convex > polygons. A triangulation algorithm (something that takes a sort of > midpoint and projects lines from each point in the polygon) is DEFINITELY > OUT of the question.....I'm trying to recover from that ;) Any help is > appreciated.... There's a paper by Chazelle & Dobkin on that exact topic: Bernard Chazelle and David P. Dobkin. Optimal Convex Decompositions. Computational Geometry, G.T. Toussaint (Editor), pages 63-133, 1985. You can also try to mail Chazelle. If I had to take a guess, I'd say his e-mail would be chazelle@cs.princeton.edu. Don't take my word for it though. Note that this is one of the only algorithms in the "convex something polytope something something" breeds which isn't NP-Complete. Most other problems are NP-Complete. The algorithm by Chazelle & Dobkin is some high degree polynomial. Sincerely yours, Sebastien Loisel ============================================================================== From: jeffe@ocarina.CS.Berkeley.EDU (Jeff Erickson) Newsgroups: comp.graphics.algorithms Subject: Re: Concave -> Convex algorithms? Date: 26 Feb 96 23:17:07 GMT ericd@ra.nilenet.com (Eric A. Drumbor) writes: > Subject says it all. I'm looking for an algorithm or even the theory >behind converting a concave polygon into a 'least number' set of convex >polygons. A triangulation algorithm (something that takes a sort of >midpoint and projects lines from each point in the polygon) is DEFINITELY >OUT of the question.....I'm trying to recover from that ;) Any help is >appreciated.... Triangulating a polygon is MUCH simpler than splitting a polygon into more complicated convex pieces. In fact, many convex partitioning algorithms (such as the simple algorithm of Hertel and Mehlhorn) start with a triangulation and delete edges. There are relatively simple polygon triangulation algorithms that run in nearly linear time. See the FAQ for more details. The optimal decomposition of an n-gon with r concave vertices, using only diagonals of the polygon, can be found in time O(r^2 n log n) = O(n^3 log n) using an algorithm due to Keil. If you allow arbitrary segments instead of just diagonals, you can get much better decompositions, but the algorithm is more complicated. In his PhD thesis, Chazelle developed an algorithm that finds the optimal convex decomposition in time O(n + r^3) = O(n^3). (See the paper by Chazelle and Dobkin.) @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" } @article{hm-ftprs-85 , author = "S. Hertel and K. Mehlhorn" , title = "Fast triangulation of the plane with respect to simple polygons" , journal = "Inform. Control" , volume = 64 , year = 1985 , pages = "52--76" , succeeds = "hm-ftsp-83" } @article{hs-oafno-81 , author = "T. C. Hu and M.-T. Shing" , title = "An {$O(n)$} algorithm to find a near-optimum partition of a convex polygon" , journal = "J. Algorithms" , volume = 2 , year = 1981 , pages = "122--138" } @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" } @book{o-cgc-94 , author = "J. O'Rourke" , title = "Computational Geometry in {C}" , publisher = "Cambridge University Press" , year = 1994 , note = "ISBN 0-521-44592-2/Pb \$24.95, ISBN 0-521-44034-3/Hc \$49.95. Cambridge University Press 40 West 20th Street New York, NY 10011-4211 1-800-872-7423 346+xi pages, 228 exercises, 200 figures, 219 references. C code and errata available by anonymous ftp from grendel.csc.smith.edu (131.229.222.23), in the directory /pub/compgeom; Third Printing: Dec. 1995" , comments = "Chapter titles: 1. Polygon triangulation 2. Polygon partitioning 3. Convex hulls in two dimensions 4. Convex hulls in three dimensions 5. Voronoi diagrams 6. Arrangements 7. Search and intersection 8. Motion planning 9. Additional topics" , update = "96.01 orourke, 95.05 orourke, 95.01 orourke, 94.05 orourke, 94.01 orourke, 95.05 orourke" , annote = "Textbook" } -- Jeff Erickson jeffe@cs.berkeley.edu http://www.cs.berkeley.edu/~jeffe