Question in Computational Geometry 6.3:

In this chapter we have looked at the point location problem with preprocessing. We have not looked at the single shot problem, where the subdivision and the query point are given at the same time, and we have no special preprocessing to speed up the searches. In this exercise and some of the following ones, we have a look at such problems.

Given a simple polygon P with n vertices and a query point q, here is an algorithm to determine whether q lies in P. Consider the ray := {(qx +,qy) : > 0} (this is the horizontal ray starting in q and going rightwards). Determine for every edge e of P whether it intersects . If the number of intersecting edges is odd, then q P, otherwise q not belong to P.

Prove that this algorithm is correct, and explain how to deal with degenerate cases. (One degenerate case is when intersects an endpoint of an edge. Are there other special cases?) What is the running time of the algorithm?