Motivation

Polygon decomposition has many applications in computer science.

Pattern recognition

Pattern recognition techniques often simplify objects into simpler components, and then use those components for identification. One way to accomplish this, is by decomposing the object into convex regions.

Computer graphics

It is often much easier to render polygons that have been broken into convex regions because of the inherent properties a convex polygon.

Physics simulations

The usage I am most interested in is for a physics simulation. Many algorithms can be performed on convex polygons much faster than they can on nonconvex polygons. For example, to determine if a point is inside a polygon, or finding the tangents from a point to a convex polygon, can both determined in logarithmic time. This is very useful for things like collision detection.

Other applications

Other applications of polygon decomposition include data compression, database systems, image processing, and VLSI art-work data processing.