New Algorithms for Computing Visibility Polygons in Computational Geometry

演讲人: Haitao Wang Utah State University
时间: 2013-01-15 14:00-2013-01-15 15:00

Computing visibility polygons is a fundamental topic in computational geometry and has been studied extensively. In this talk, I will discuss our recent progress on developing algorithms and data structures for computing visibility polygons. We consider the problem of computing the visibility polygon from an island (a simple polygon) in a polygon with holes. Previously, only the special case where the island is a line segment has been studied. We give the first-known algorithm for the general problem and our algorithm is even better than the previous solution for the special case. Our algorithm is also worst-case optimal. I will also discuss our new results on some query versions for computing visibility polygons, which include computing visibility polygons from query points in polygons with holes and computing visibility polygons from query line segments in simple polygons. In addition, as a special visibility problem, we also obtain new algorithms and data structures for solving ray-shooting queries in polygons with holes.