Show that, given a query point q, it can be tested

Question

I am trying to solve some exercises of the book "Computational Geometry Algorithm and Applications, 3rd - de berg et al" of chapter 6 - Point Location. Unfortunately, I have no idea how to solve the following exercise:

Given a convex polygon P as an array of its n vertices in sorted order
along the boundary. Show that, given a query point q, it can be tested in
time O(log n) whether q lies inside P.

My Idea so far: The only way I know to determine if a point lies inside p in O(log n) is to use a directed acyclic graph. In order to use a directed acyclic graph I need to build it, which is impossible in O(log n). So, somehow I need to use the ordered array, but the only solution I know with an array will cost O(N).

I hope that someone could help me.

Answer 1

The idea is basically to do a binary search, to find which 'segment' the point belongs to. The assumption here is that the polygon wraps around some fixed origin O, which is necessary to define an angular sorting routine.

To find whether q lies on the 'left' or 'right' of P[n/2] (by which I mean an anticlockwise or clockwise rotational difference about O), we do the 2D cross-product:

This is a real scalar. If this is positive, then a is to the right of b, and vice versa. In our code a = q - O and b = P[i] - O, where i is the index of the point on the polygon we are testing q against.

We can then use this test to find which 'segment' or 'wedge' q is in, i.e. which points of the polygon q is between (on the diagram these are P[n/2 - 1] and P[n/2]), using a binary search, which is O(log n). (I'll assume you know how to do this)

Once we know that, we need to know whether q is inside the 'wedge'.

From https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection, for two lines defined by pairs of points [(x1, y1), (x2, y2)] and [(x3, y3), (x4, y4)] respectively, their intersection point (Px, Py) is given by

Compute the intersection between [Pl, Pr] and [q, O] to give s, and compute the distance |s - O|. If this is greater than |q - O| then q is inside the polygon P, and vice versa.

(This step is of course O(1). There may however be more elegant ways of doing it - I'm just illustrating the logic behind it)

The total complexity is then O(log n) + O(1) = O(log n).