Question

In an answer to the problem of determining whether or not a point lies inside a given convex hull, a thesis is mentioned, which says :

For repeated queries with preprocessing allowed, we develop a special method that relies on the convexity of the polygon. Recalling Theorem 3.5, the vertices of a convex polygon occur in angular order about any interior point. Find such a point O and consider the N rays from O that pass through the vertices of P. (Figure 4.8.) These rays partition the plane into N pie-shaped wedges. Each wedge is divided into two pieces by a single edge of P. One of these pieces is wholly interior to P, the other wholly exterior. Treating O as the origin of polar coordinates, we may find the wedge in which z lies by a single binary search, since the rays occur in angular order.

How would one do the binary search (assuming the convex hull's vertices are given in counter-clockwise order)?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top