Search code examples
algorithmcomputational-geometrypoint

Algorithm for finding the maximum number of points

Let P = {P1(x1, y1), P2(x2, y2), . . . , Pn(xn, yn)} be a set of n points located within a rectangle such that none of the points touches its boundary. The top-left corner of the rectangle is at the origin O(0, 0). A plane mirror is placed along the lower edge of the rectangle (as shown in the figure). A point source of light is placed at O. The source can emit a single ray of light at any angle θ.

enter image description here

Write an algorithm (pseudo-code) to compute a value of θ for which the corresponding ray and its reflection together pass through the maximum number of points of the set P.

For example, in the figure, the ray R1 at angle θ1 (denoted by a solid line), passes through 3 points, while the ray R2 at angle θ2 (denoted by a dashed line), passes through only 2 points. You will get full credit only if your algorithm takes O(n log n) time.

................................................

I would have done this problem if it was to find the value of θ such that the maximum number of points on the plane lies on the incident ray.

At that time I would have calculated the value of θ for each point by focusing the light ray on each point and store the values of θ for the points in an array.

Then our problem would be reduced to finding the maximum number of repeated element in an array. That could be solved in O(n) time.

But I don't know how to handle the reflected ray. I searched in the internet but in vain. Please help.

Solution

  • One approach would be to use the method of images, which replaces the effect of reflections by introducing 'mirror points' on the opposite side of the reflecting surface.

    Suppose that the mirror is defined by the plane y=-b, then each point (x_i, y_i) would be used to generate a reflected version of itself. That extra point would have the same x-coordinate, but have a y-coordinate on the symmetrically opposite distance from the mirror, i.e. -b - (y_i + b) which is -2b - y_i. (In your case, all the y_i are negative.) This reflected version of each point exactly models the geometry of a ray that reaches the original point after bouncing off the mirror. Thereafter, we can ignore the mirror, and just work with 2N points.

    So, the pseudo code for your algorithm might run something like this:

    • Generate an additional set of N points below the mirror surface using the method of images
    • Calculate the angle of each of the 2N points from the origin, using atan2(y_i, x_i). This takes time of order N.
    • Group the points by their angles from the origin, which is equivalent to sorting them and detecting changes between adjacent values in a list, which takes time of order N(log N).
    • Count the number of points in each group. (This takes time less than N.)
    • Find the group with the largest number of members.