Create a function and find parameter values for maximum

Question

I have may be a strange question about the task that I was asked during an interview (actually I am a software developer, so I cannot know for sure).

The question:

You are staying at the beginning of coordinates with a camera with the viewing angle $\alpha$.

There are many trees around you with the coordinates $(x_1, y_1), (x_2, y_2) \cdot (x_n, y_n)$.

What is the algorithm to find from which angle $\beta$ (relatively to the coordinate axis) should you make a shot of the maximal number of the trees (if one tree is staying behind another one it is considered to be on the shot).

The only algorithm that was suggested to me was a variation of brute-force:

1. to convert the cartesian coordinates into the polar ones
2. sort the trees by the angle value
3. to approximately n shots jumping from tree to tree
4. count which photo contains the maximum trees

And I had another idea: a shot can be defined by $2$ half-lines

• $y=ax+b$ and
• $y=f(\alpha, a)x + f(\alpha, b)$

and for all the particular values of the parameters $a$ and $b$ we can always say if a tree $(x_i, y_i)$ is placed between the half-lines (comes into the shot) or not.

Is there any possibility (for the given $(x,y)$-pairs) to build a function in such a way that it is possible to find out which values the parameters $a$ and $b$ should have that the result of the function (the number of the trees) is the maximal?

Answer 1

More explicitly than in the comment, I would fix an algorithm along the following steps.

a) convert the $n$ points into polar coordinates $(r_k, \beta_k)$;
b) determine the range $b = \beta_{max} - \beta_{min}$ of the angles, in the limit $b=2 \pi$;
c) we want to construct a "frequency histogram" of the $\beta_k$'s: to this purpose we need to fix an adequate cell-width $\Delta b = b/m$ by dividing the angle range into $m$ equal intervals;
d) for fixing $m$ we need to balance between two opposite exigencies:
- the average content $n/m$ should be high enough to clearly individuate where the maximum (or maxima) are located,
- $\Delta b$ shall be comparable, possibly smaller, than the camera view angle.
e) the above exigencies much depend on the actual data, so you need some preliminary facts/assumptions concerning them and choose the best $m$;
f) construct the frequency histogram/table, determine the single or multiple maxima, by fixing a suitable threshold, which again depends on the data structure: these are the angles at which to take the shots.