### Technical Report No. 52, April 1994 - Abstract

**Sven Schuierer:**

*An O(log log n) Algorithm to Compute the Kernel of a Polygon*

The kernel of a polygon **P** is the set of all points that see the
interior of **P** . It can be computed as the intersection of the
halfplanes that are to the left of the edges of **P**. We present an
*O(log log n)* time CRCW-PRAM algorithm using *n/(log log n)*
processors to compute a representation of the kernel of **P** that
allows to answer point containment and line intersection queries
efficiently. Our approach is based on computing a subsequence of the
edges that are sorted by slope and contain the "relevant" edges
for the kernel computation.

report52.ps.gz