SHORTEST PATHS WITH SINGLE-POINT VISIBILITY CONSTRAINT
Ramtin Khosravi, Mohammad Ghodsi · Scientia Iranica · 2006
This paper studies the problem of finding the shortest path between two points in presence of single-point visibility constraints. In this type of constraints, there should be at least one point on the output path from which a fixed viewpoint is visible. The problem is studied in various domains including simple polygons, polygonal domains, polyhedral surfaces. The method is based on partitioning the boundary of the visibility region to a number of intervals according to shortest path structure of their points to both source and destination. The result for the two dimensional domains is worst-case optimal.