Find the square with the most points

Question

HELLO!

MY FRIEND WAS DOING SOME ONLINE QUESTIONS AND RAN INTO THIS ONE WHERE WE ARE COMPLETELY STUCK.

PROBLEM: IF WE ARE GIVEN A SET A CONTAINING NON-OVERLAPPING SQUARES OF THE SAME SIZE, AND A SET B CONTAINING SCATTERED POINTS ON A GRID.

HOW CAN WE DEFINE A DIVIDE AND CONQUER ALGORITHM O(NLOGN) TO FIND THE SQUARE WITH THE MOST POINTS? WHERE N = |A| + |B|

ANY HELP WOULD BE APPRECIATED!!

Answer 1

Nino_c looks like my assumptions are correct. The format for the squares is still not clear, but applying the described logic should be straight forward in any case

Answer 2

Martin Taylor problem is really easy to solve with a brute force approach. Im finding it hard to do it with a divide and conquer approach which is a requirement for the correct answer
Thanks for helping though!

Answer 3

Martin Taylor thanks for the clarification!

Answer 4

Martin Taylor i realized, i tried to change it to lower case but it keeps going back to uppercase in the question body. I think its bugged

To clarify, each point has an (int, int) coordinate, and the squares are placed to vertically align and each corner is also a 2d point wirh (int, int) coordinate, so we are trying to find the square that overlaps with the most points.

Note that the squares all have a common side length and they are not overlapping (no two squares share a coordinate whatsoever)

Answer 5

I assume the squares can't be rotated, i.e. the sides must be parallel to the axis.
Non-overlapping of the squares doesn't matter and to find the solution maybe it is easier to generalize to rectangles.
A rectangle can then be defined by its min and max values for x and y respectively.
Tjen think about this: How can you define if a point is inside the rectangle by comparing its coordinates with those 4 values?
I hope my assumptions are correct, if not please clarify your question

Answer 6

Benjamin Jürgens yes your assumptions are correct.
I understand that we have the min and max corners we can then just test if a point is within the boundaries of the rectangle,
Where im struggling is how can i define the subproblems and recuse on the independently to find a solution in O(N log N) where N = |squares| + |points|