1
$\begingroup$

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)

enter image description here

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

enter image description here


Related question on stackoverflow

$\endgroup$
2
  • 1
    $\begingroup$ 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) $\endgroup$
    – Nathaniel
    Feb 23 at 22:10
  • $\begingroup$ The naive approach runs in linear time, which is a tight bound. $\endgroup$ Feb 26 at 14:52

1 Answer 1

2
$\begingroup$

The naive approach is the following two steps:

  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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.