title: Finding a ray that intersects a polygon as many times as possible
body: <p>Here is an interesting exercise:</p>
  
  <blockquote>
    <p>Let P be a simple, but not necessarily convex, polygon and q an arbitrary point not necessarily in P. </p>
    
    <p>Design an efficient algorithm to find a line segment originating from q that intersects the maximum number of edges of P. </p>
    
    <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?</p>
    
    <p>A bullet through a vertex of P gets credit for only one wall. </p>
    
    <p>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.</p>
  </blockquote>
  
  <p>Here is my thought:</p>
  
  <p>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.</p>
  
  <p>The final shooting line must be in between these pairs. So we must find the pair that contains the largest number of edges.</p>
  
  <p>I don't think this solution  is O(n log n).</p>
  
  <p>Any ideas?</p>