3
$\begingroup$

Point $q$ is a kernel of a polygon $P$ if from $q$ we can see all vertices of $P$.

In addition, kernel is a intersection of $N$ half planes formed by edges of polygon.

Proofs of the above statements can be found in Visibility and Kernel of Polygon.

I try to figure out what the efficient way of testing if point $q$ is kernel or not.

The most naive way is to construct intersection of $N$ half spaces of polygon $P$, it should take $O(nlogn)$ and then check if point $q$ belongs to intersection of half spaces. So, all this process should take $O(nlogn)$.

I assume that more efficient way should exist.

1 Answers 1

4

The intersection of the halfspaces can in fact be computed in linear time, $O(n)$, by carefully exploiting the ordering provided by the polygon's boundary. This is established in a 1979 paper by Lee & Preparata, "An Optimal Algorithm for Finding the Kernel of a Polygon" (ACM link).

Once you have the kernel as a convex polygon, it is straightforward to check if $q$ lies inside it in time proportional the the number of edges $k \le n$ of the kernel.

  • 0
    thanks you very much for the paper!2012-06-05