Decomposing a polygon into its convex parts

ABSTRACT

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.

REFERENCES

• 1: Dobkin,D., Keyword structures in a language for computer geometry, Bell Laboratories Technical Memorandum, TM 78-1271-9, June 29,1978.
• 2: Dobkin,D. and Lipton,R., Multidimensional searching problems, SIAM Journal on Computing, Vol. 5, No. 2, June 1976, pp. 181-186.
• 3: Dobkin,D. and Snyder,L., On a general method of maximizing and minimizing among certain geometric problems, in preparation.
• 4: Dobkin,D. and Tomlin,D., Cartographic modelling techniques in environmental planning: an efficient system design, submitted for publication.
• 5: Feng,H. and Pavlidis,T., Decomposition of polygons into simpler components: feature generation for syntactic pattern recognition, IEEE Transactions on Computers, Vo. C-24, No. 6, June 1975, pp. 636-650.
• 6: Garey,M., Johnson,D., Preparata,F., and Tarjan,R., Triangulating a simple polygon, Information Processing Letters, Vol. 7, No. 4, June 1978, pp. 175-180.
• 7: Lloyd,E., On triangulations of a set of points in the plane, 18th Annual IEEE FOCS Conference Proceedings, Providence, R.I., October 1977, pp. 228-240.
• 8: Pavlidis,T., Analysis of set patterns, Pattern Recognition, Vol. 1, 1968, pp. 165-178.
• 9: Shamos,M., Geometric Complexity, PhD Thesis, Yale University, May 1978.
• 10: Volecker,H. private communication to D. Dobkin, November 14, 1977.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

General Terms:
Algorithms, Theory