TY - JOUR

T1 - Decomposing a polygon into its convex parts

AU - Chazelle, Bernard

AU - Dobkin, David

N1 - 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 -