The Power of Triangulation: Applications to Problems of Visibility and Internal Distance

摘要

It is well-known that the complexity of performing operations on a set depends heavily on the structure which we are allowed to put into its representation. For example, searching through a sequence of numbers can be performed more efficiently if the numbers appear in sorted order. In this paper, we take, as a case-study, the class of problems involving a simple N-gon P and, making the assumption that in addition to the usual description of the boundary of P, an arbitrary triangulation is also available, we investigate the computational power gained from having this additional information. Among other results, we give a very simple, optimal algorithm for computing the area visible from an arbitrary point in P. We also present several optimal algorithms for computing the internal distance between two points in P. Recall that the internal distance between A and B is defined as the length of the shortest path inside P between A and B. (Author)