Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
thanks you very much for the paper! –  com Jun 5 '12 at 19:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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