An efficient algorithm for computing the K-overlapping maximum convex sum problem

This research presents a new efficient algorithm for computing the K-Maximum Convex Sum Problem (K-MCSP). Previous research has investigated the K-MCSP in the case of disjoint regions. In this paper, an efficient algorithm with O(Kn3) time is derived for the overlapping case. This approach is implemented by utilizing the simplified (bidirectional) algorithm for the convex shape. This algorithm finds the first maximum sum, second maximum sum and up to the Kth maximum sum, based on dynamic programming. Findings from this paper show that using the K-Overlapping Maximum Convex Sum (K-OMCS), which is a novel approach, gives more precise results when compared with the results obtained from the rectangular shape. Additionally, this paper presets an example for prospective application of using the Maximum Convex Sum Problem (MCSP) to locate a cancer tumour inside a mammogram image