Convex Partitioning

Algorithm: M. Dutt, A. Biswas, and P. Bhowmick, Approximate Partitioning of 2D Objects into Orthogonally Convex Components, Computer Vision and Image Understanding, Vol. 117(4), pp. 326-341, 2013. A preliminary version appeared in Proc. DGCI-2011, LNCS (Springer) vol. 6607, pp. 489-500, 2011. Why: Polygons are frequently used by practitioners to solve geometric problems related with image processing and computer vision. Computational-geometric problems on general polygons are solved usually by decomposing them into simpler components, solving the problem for each component using a specialized algorithm, and then combining the partial solutions. A polygon can be decomposed into rectangular components, convex components, star-shaped components, monotone components, etc. How: Polygon decompositions can be classified based on the interrelation among decomposed components. If the components do not overlap except at their boundaries, then the decomposition is termed as a partition. If overlapping pieces are allowed, then it is called a cover. Decomposing a polygon into simpler components can be performed with or without addition of extra vertices, which makes the problem complex but leads to fewer components.

A decomposition must be minimal in some sense. Some applications use decomposition of a polygon into minimum number of components, and some other applications use decomposition that minimizes the total length of internal edges. Several interesting works are found on decomposition in general domain as well as in orthogonal domain. In general domain, decomposition of a polygon with holes into minimum number of components is NP-hard, whether allowing or disallowing Steiner points. Allowing Steiner points, an O(n log n)-time approximation algorithm under minimum edge-length criteria was proposed by Levcopoulos and Lingas (1984). No optimal algorithm is known for decomposing hole-containing polygons when Steiner points are allowed; it has been shown by Lingas et al. (1982) that such problems are NP-hard. In 3D domain also, several works have been done; some approximation algorithms are given by Lien and Amato (2006), and by Aguilera and Ayala (2000). Our algorithm is designed in a manner so as to decompose 2D digital objects into orthogonally convex components, which might be useful for shape representation, shape analysis, and shape matching. For example, the partition may be used to generate convex decomposition graph to estimate shape complexity. The algorithm can decompose a hole-free orthogonal polygon into a nearly optimal set of convex pieces in O(nlogn) time by considering all the concavities of the polygon. The steps are based on the rules designed out of combinatorial possibilities.

A digital shape.	Its maximal inner isothetic cover.	Its convex decomposition.
© Partha Bhowmick (November 2012)