The Superman problem |
| |
| Authors: | Naji Mouawad Thomas Shermer |
| |
| Affiliation: | (1) Department of Computer Science, University of Waterloo, N2L 3B1 Waterloo, Ontario, Canada;(2) School of Computing Science, Simon Frazer University, V5A 1S6 Burnaby, British Columbia, Canada |
| |
| Abstract: | Given a polygonK contained in a polygonP, and a points lying outsideP, we present a  (n logn) algorithm that finds the minimum number of edges, ofP that we want to retain in order to hidek froms. Furthermore, if the visibility polygon ofs givenK is unbounded, the algorithm is shown to run in linear time. This paper is dedicated to J. Siegel and J. Shuster.This work was supported by Friends of McGill Fellowship while T. Shemer was at McGill University. |
| |
| Keywords: | Computational geometry Visibility Trapezoidization Circlecover minimization Lower bound |
| 本文献已被 SpringerLink 等数据库收录！ |
|
