$(2).5$ points Build the Kirkpatrick point location hierarchy for the triangulation shown below. At each step, when you identify an independent set, apply Algorithm $7\mathrm{.}4$ on page $277,$ breaking ties when you select a node in favor of the lowest numbered vertex. When you retriangulate a hole, use the simple ear$-$clipping algorithm $($Triangulate$,$ page $39),$ starting at the bottommost vertex of the hole $($as $"$vO$"$ in Triangulate, the first one tested for earity$),$ and proceeding counterclockwise. $($Ties $($if any$)$ for bottommost should be broken by picking the rightmost among the bottommost vertices.

$($a$).$ List the independent sets corresponding to each stage of the algorithm.

Also, for each stage, draw the corresponding triangulation. To assist you with this, I have printed copies of the vertices of the original input, on the next page $($you may want to print multiple copies of that page$).($b$).$ Draw the final hierarchy as a DAG, with each node of the hierarchy labeled by the triangle to which it corresponds. $($When you label a node, please list the triangle as a triple with the vertex indices in order; e$.$g$.,$ the triangle with vertices $"1","8"$ and $"9"$ should be written as $"189"($not as $"819"$ or $"918",$ etc$).)($c$).$ Highlight in the final hierarchy those nodes that are explored when point location is performed for

point p$,$ as shown in the figure.

$($d$).$ Identify a point q$,$ not in the face at infinity, $($and draw it in the figure$)$ for which the number nodes

of the hierarchy that are explored and highlighted $($as in part $($c$)$ for point p$)$ is minimized.