Abstract:
Consider a simple polygon P and a point s on the frontier @P of P. For any real > 0 there exists a shortest path inside of P such that s is on the path , and for each point p in @P, there exists a point q in at Euclidean distance less than or equal to p such that the line segment pq is in P. Such an optimum path is called a shortest route for @P visibility under -visibility that starts at point s on @P. We provide an approximation algorithm (which belongs to the class of rubberband algorithms) for finding such a path in O(n2) run time, where n is the number of vertices of a given simple polygon P. The run time does not depend on or on the start point s.