Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 3 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|cite|improve this answer
thanks you very much for the paper! – com Jun 5 '12 at 19:06

Your Answer


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.