Given a set of points S in a 2 dimensional coordinate plane, where all points in S have positive integer coordinates. We need to calculate a function g(S) that returns the minimum sum of side length l (of an lxl square) of all squares that are required to cover all points in the set S (Any point lying on or inside a square's parameter is covered by it). The squares have to be axis-parallel and can be overlapping or non-overlapping. Each square may or may not have the same side length. Every square's side length must also be a positive integer (>=1).
Here's an example: Example Image
The blue dots represent the points in set S. I've shown 2 ways to cover them using squares.
- One red square of length 3 covers all points. Total sum: 3;
- Two green squares of length 1 each. Total sum: 1+1=2;
So in this particular example, g(S) = 2;
I was wondering if there is a solid algorithmic way to solve a problem like this?