A simple polygon P is called star$-$shaped if there exists a

point p in P such that for every point q in P $,$ the line segment pq lies in P $.$ Hence, p can $$see$$ any point in

P by a line of sight entirely in P $.$ You are given a simple star$-$shaped polygon P $,$ described as an array of n

vertices in counterclockwise order about P $.$

$($i$)$ Suppose you know a point p that can see all of P $.$ Describe an algorithm that determines whether a

point q is in P in O$($log n$)$ time $($with no preprocessing$).$

$($ii$)$ Suppose you don$$t know a point p that can see all of P $.$ Describe an optimal algorithm for finding

one, and give its asymptotic running time. $($Hint: this is a one$-$liner.$)$

$($iii$)$ Explain why no algorithm can find one faster, even if you know in advance that P is star$-$shaped.

$($Hint: this is not a reduction from sorting. Show that the algorithm must examine the entire input or at

least some constant fraction of it$.$ A few examples where small differences between two star$-$shaped

polygons lead to completely different answers will help your explanation.$)$

$($iv$)$ Can your algorithm from part $($ii$)$ also determine whether a simple polygon P is star$-$shaped? Can it

extend to three$-$dimensional polyhedra, and if so$,$ what is the asymptotic running time of the extended

algorithm? Briefly justify your answers to both these questions