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.