AbstractThe 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(loglog n) time CRCW-PRAM algorithm using n/loglog 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.
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.