0
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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

enter image description hereenter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.