Convex partitioning of a polygon into smaller number of pieces with lowest memory consumption

Abstract

Designing an algorithm to deal with a convex shape is easier than that for a concave shape. Efficient algorithms are required to process concave shapes, because every application does not deal with convex shapes. An alternative approach is to first transform a concave shape into a set of convex shapes so that efficient algorithms available for convex shapes can be utilized. This paper proposes an algorithm for partitioning a concave polygon into smaller number of convex pieces. Each resultant convex piece then can be processed using a simple algorithm applicable to convex shapes. In this way, any arbitrary shape can be processed using such simple algorithms with the aid of the proposed algorithm. There are plenty of algorithms available in literature to solve convex partitioning problem. Hertel Mehlhorn algorithm is the most efficient algorithm, but it does not minimize the number of convex pieces satisfactorily. Further the Hertel Mehlhorn algorithm is the minimum memory consuming algorithm available in literature. Later Geene proposed an algorithm which gives the minimum number of convex pieces. It uses dynamic programming technique and needs high amount of memory. Therefore Geene’s algorithm is not suitable for systems where the memory is limited. Chazelle proposed an efficient algorithm which gives minimum number of convex pieces. However a data structure to implement Chazelle’s algorithm is not available in literature. The experimental results showed that the proposed algorithm gives smaller number of convex pieces than the Hertel Mehlhorn algorithm. The memory consumption of the proposed algorithm is also lower than the Hertel Mehlhorn algorithm.

Keywords

• computational geometry, computer graphics programming, coordinate geometry, euclidian geometry, computer programming