TY - JOUR
T1 - Decomposing a polygon into its convex parts
AU - Chazelle, Bernard
AU - Dobkin, David
N1 - Funding Information:
Our analysis of the problem begins with the introduction of X-patterns from which all decompositions may be generated. An Xk-pattern is an interconnectlon of k notches forming a set of k polygons which remove all reflex angles occuring at the k notches and create no new notches. A complete decomposition will consist of a set of k Xij-patterns along with k' notches used to remove *This research was started when the second author was at Yale. Portions of the research were supported by the Office of Naval Research under Grant N00014-75-C-0450 and the National Science Foundation under Grant MCS76-11460.
Funding Information:
This research was also facilitated by the use of theory net, NSF Grant MCS78-01689.
Publisher Copyright:
© 1979 Association for Computing Machinery. All rights reserved.
PY - 1979/4/30
Y1 - 1979/4/30
N2 - A common operation in geometric computing is the decomposition of complex structures into more basic structures. Since it is easier to apply most algorithms to triangles or arbitrary convex polygons, there is considerable interest in finding fast algorithms! for such decompositions. We consider the problem of decomposing a simple (non-convex) polygon into the union of a minimal number of convex polygons. Although the structure of the problem led to the conjecture that it was NP-complete, we have been able to reach polynomial time bounded algorithms for exact solution as well as low degree polynomial time bounded algorithm/or approximation methods.
AB - A common operation in geometric computing is the decomposition of complex structures into more basic structures. Since it is easier to apply most algorithms to triangles or arbitrary convex polygons, there is considerable interest in finding fast algorithms! for such decompositions. We consider the problem of decomposing a simple (non-convex) polygon into the union of a minimal number of convex polygons. Although the structure of the problem led to the conjecture that it was NP-complete, we have been able to reach polynomial time bounded algorithms for exact solution as well as low degree polynomial time bounded algorithm/or approximation methods.
UR - http://www.scopus.com/inward/record.url?scp=84985396016&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84985396016&partnerID=8YFLogxK
U2 - 10.1145/800135.804396
DO - 10.1145/800135.804396
M3 - Conference article
AN - SCOPUS:84985396016
SN - 0737-8017
SP - 38
EP - 48
JO - Proceedings of the Annual ACM Symposium on Theory of Computing
JF - Proceedings of the Annual ACM Symposium on Theory of Computing
T2 - 11th Annual ACM Symposium on Theory of Computing, STOC 1979
Y2 - 30 April 1979 through 2 May 1979
ER -