I am trying to understand triangulation, explained in the book "Computational Geometry Algorithms and Applications, 3rd Ed - de Berg et al". Unfortunately, I don't know how to solve the following question:
The pockets of a simple polygon are the areas outside the polygon, but inside its convex hull. Let $P_1$ be a simple polygon with m vertices, and assume that a triangulation of $P_1$ as well as its pockets is given. Let $P_2$ be a convex polygon with n vertices. Show that the intersection $P_1 \cap P_2$ can be computed in O(m + n) time.
The problem is that I do not know how I can use the triangulation of $P_1$ to calculate the intersection of $P_1$ and $P_2$.
A much simpler version of this problem is the intersection of two convex polygons which can be calculated in $O(m+n)$ time as well using the plane-sweep method where $n+m$ vertical sweep-lines partition the plane into $n+m-1$ vertical slabs. I thought it would be adequate to simply expand this concept for this problem but it proved to be insufficient. Instead, I came across a possible solution online:
http://www.ics.uci.edu/~goodrich/teach/cs266/hw/solution3.pdf