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