Visibility of disjoint polygons |
| |
| Authors: | Takao Asano Tetsuo Asano Leonidas Guibas John Hershberger and Hiroshi Imai |
| |
| Affiliation: | (1) Faculty of Science and Technology, Sophia University, 102 Tokyo, Japan;(2) Osaka Electro-Communication University, Neyagawa, 572 Osaka, Japan;(3) Computer Science Department, Stanford University, 94305 Stanford, California, USA;(4) DEC Systems Research Center, 94301 Palo Alto, California, USA;(5) Department of Mathematical Engineering and Instrumentation Physics, Faculty of Engineering, University of Tokyo, 113 Tokyo, Japan |
| |
| Abstract: | Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n
2) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n
2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n
2) time, improving earlierO(n
2 logn) results. |
| |
| Keywords: | Computational geometry Computer graphics Robotics Visibility Hidden-line Elimination Visibility graph Shortest path |
| 本文献已被 SpringerLink 等数据库收录！ |
|
