Given a planar subdivision $S$, prove that the face of $S$ containing a point $q$ can be computed in linear time

Question

Show that, given a planar subdivision $S$ with $n$ vertices and edges and a query point $q$, the face of $S$ containing $q$ can be computed in time $\mathcal{O}(n)$. Assume that $S$ is given in a doubly-connected edge list

Answer 1

It's a fundamental problem of computational geometry, which can be solved in $O(log(n))$ time provided that the pre-processing of the planar subdivision $S$ is allowed.

Please read this page for more info.