AbstractThe kernel of a polygon

Pis the set of all points that see the interior ofP. It can be computed as the intersection of the halfplanes that are to the left of the edges ofP. We present anO(loglogn) time CRCW-PRAM algorithm usingn/loglognprocessors to compute a representation of the kernel ofPthat 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.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems

Additional Key Words and Phrases: computational geometry, visibility, polygons, kernel

Selected references

- Mikhail J. Atallah, Danny Z. Chen, and Hubert Wagener. An optimal parallel algorithm for the visibility of a simple polygon from a point. Journal of the ACM, 38(3):516-533, July 1991.

- Paul Beame and Johan Hastad. Optimal bounds for decision problems on the CRCW PRAM. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 83-93, New York City, 25-27 May 1987.

- D. T. Lee and F. P. Preparata. An optimal algorithm for finding the kernel of a polygon. Journal of the ACM, 26(3):415-421, July 1979.

- Hubert Wagener. Optimal parallel hull construction for simple polygons in \cal{O}(log log
n) time. In 33rd Annual Symposium on Foundations of Computer Science, pages 593-599, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.