Region inter-visibility in terrains

Abstract

A polyhedral terrain is the image of a piecewise linear continuous function de ned over the triangles of a triangulation in the xy- plane. Given a terrain with n vertices, two simply-connected regions (subsets of the triangles), and any constant e > 0, we an determine in O(n2+e) time and storage whether or not the two regions are completely inter-visible, which improves the O(n3) time complexity of a brute-force algorithm.