A bullet through a vertex of p gets credit for only one


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.

Request for Solution File

Ask an Expert for Answer!!
Basic Computer Science: A bullet through a vertex of p gets credit for only one
Reference No:- TGS02161556

Expected delivery within 24 Hours