How to identify a continuous shape and break it into minimum number of rectangles?

The input in this case is going to be coordinates in 2D of the vertices of the shape. There will be no curves, but the shape can have holes. The algorithm or program needs to identify the continuous shape and break it into rectangles. The number of rectangles so created has to be optimized too.

I did read about spatial segmentation, but I am confused how to implement it. Any suggestions or help will be greatly appreciated.

Thanks!