# Algorithm to split a grid into different shapes of similar area

I was wondering if any of you know of any algorithm which allows me to split a grid into smaller shapes of a similar area.

I have a grid and a few points, these points determine the center of the shape. For example, in a 100x100 grid, if I have 4 points at the following coordinates: (25,25),(25,7) ,(75,25), (75,75) I will have 4 square shapes of equal size in 4 corners of the grid.

However, there are instances where I would have less/more than 4 points and at locations that may be trickier, for example, 6 points at the following coordinates: (14,12), (18,24), (74,41), (82,31), (04,72), (37,12)

I am aware that if the above was the case, the shapes won't be of equal sizes, but my goal is to try to have a similar area between all shapes.

Thank you for the help

• What do you mean by "center of the shape"? Apart from the center being part of the shape, are there other conditions on the shapes? – RcnSc Jan 3 at 12:30
• Sorry, I meant the point has to be in the shape, it doesn't need to be at the center of the shape. – Darryl Soh Soon Yong Jan 4 at 9:13