11

Here is an interesting exercise:

Let P be a simple, but not necessarily convex, polygon and q an arbitrary point not necessarily in P.

Design an efficient algorithm to find a line segment originating from q that intersects the maximum number of edges of P.

In other words, if standing at point q, in what direction should you aim a gun so the bullet will go through the largest number of walls?

A bullet through a vertex of P gets credit for only one wall.

An O(n log n) algorithm is possible. n is the number of vertices or edges, as it is a polygon, number of edges roughly equals to number of vertices.

Here is my thought:

Connect q with all vertices (let's say there are N vertices) in P first. There will be N lines, or N-1 pairs of lines.

The final shooting line must be in between these pairs. So we must find the pair that contains the largest number of edges.

I don't think this solution is O(n log n).

Any ideas?

Pops
  • 30,199
  • 37
  • 136
  • 151
Jackson Tale
  • 25,428
  • 34
  • 149
  • 271
  • Wow., I have no idea. Out of curiosity, what is n here? The number of edges? – Jeremy May 06 '12 at 21:11
  • I believe this question is related: http://stackoverflow.com/questions/4446112/search-for-interval-overlap-in-list-of-intervals You can express each line segments in P as a pair of radian values that a ray from q must fall between. – Sam Dufel May 06 '12 at 21:13
  • @Jeremy I edited. yes n can be num of edges or vertices, roughly the same in polygon. – Jackson Tale May 06 '12 at 21:54

2 Answers2

10

Well, first transform the points coordinates into a polar system centered at P.

  • Without loss of generality, let's choose clockwise direction as special with respect to the angle coordinate.
  • Now let's conduct a circular walk in sequence along all the edges of the polygon, and let's notice the starting and the ending point of those edges, where the walk takes us in the clockwise direction with respect to P.
  • Let's call the ending point of such edge a 'butt', and the starting point a 'head'. This all should be done in O(n). Now we'll have to sort those heads and butts, so with quicksort it might be O(nlog(n)). We are sorting them by their angle (φ) coordinate from the smallest φ up, making sure that in case of equal φ coordinate, heads are considered smaller than butts (this is important to comply with the last rule of the problem).
  • Once finished, we'll start walking them from the smallest φ, incrementing the running sum whenever we encounter a butt, and decrementing whenever we encounter a head, noticing a global maximum, which will be an interval on the φ coordinate. This should be also done in O(n), so the overall complexity is O(nlog(n)).

Now would you tell me why are you asking this kind of questions?

Anirudh Ramanathan
  • 46,179
  • 22
  • 132
  • 191
Boris Stitnicky
  • 12,444
  • 5
  • 57
  • 74
  • Thank you for answering this question. Could you please edit your answer to look more nicely? – Jackson Tale May 06 '12 at 21:52
  • This is an excise in Algorithm Design Manual. – Jackson Tale May 06 '12 at 21:52
  • Can anybody explain this soln in little bit details, especially the 3rd and 4th point @BorisStitnicky – KingJames Jun 18 '14 at 18:48
  • @KingJames, with time, I realize that the wording could be improved. But I won't do it. You can edit the answer if you like, but I think that as it is now, it is sufficient to stimulate thinking in the right direction, especially considering that this is basically a homework assignment. – Boris Stitnicky Jun 19 '14 at 05:48
  • I have a question. Do you know how to make a clockwise or counterclockwise walk correctly? It seems to me that if P lies inside the polygon than there is an ambiguity. The last edge of the polygon will intersect φ = 0 direction, but φ value of interval's HEAD will be less than φ value of BUTT. – Michael Katkov Jan 23 '15 at 18:31
  • I found out that the cross product is a good solution for this problem. – Michael Katkov Jan 26 '15 at 05:47
1

I used algorithm of Boris Stitnicky and wrote my solution in Java. But I chose counterclockwise direction, and to check what point of an interval is the start point and what point is the end of an interval I used the cross product. You can find it here: https://github.com/Katkov/algorithms/blob/master/BulletAgainstWalls.java

Michael Katkov
  • 2,256
  • 1
  • 20
  • 17