# Algorithm that finds points that are closest to the middle of rectangles in grid

Suppose I have an array of 2D coordinates {x:number,y:number}[]. What would be an algorithm that could get me the points that, were an X by Y grid of rectangles laid over the cartesian graph created by the array, are closest to the middle of each rectangle that contains points?

Here's a very roughly drawn example:

• 22 (x,y) points
• The top, right, bottom, and left bounds of the imaginary grid are based on the topmost, rightmost, bottommost, and leftmost points.
• This particular grid is broken up into 16 rectangles. The width of all rectangles is the same and the height of all rectangles is the same (though the width might not equal the height)

In this case, the algorithm would return the coordinates of the 13 dots below (again roughly drawn. Some dots were close!).

Related question on stackoverflow

• What's the problem with a naive approach? (compute the distance of each point to its respective rectangle center and keep the minimum for each rectangle) Commented Feb 23 at 22:10
• The naive approach runs in linear time, which is a tight bound. Commented Feb 26 at 14:52

1. For each point, insert it into its respective box in $$O(n)$$.
2. For each box, iterate every point in it to keep track of the minimum distance to the center and return the point in $$O(n)$$.
There is no faster algorithm as reading the inputs already takes $$O(n)$$.