Some visibility problems for isothetic objects and a simple polygon

Abstract

This thesis is concerned with the notion of visibility in two and three dimensional objects. Two kinds of visibility problems are considered: the visibility in isothetic objects and the internal line visibility of a simple polygon. We introduce the two and three dimensional visible points problems as basic visibility problems for isothetic objects: determine all points in a given point set that are visible from a viewpoint at infinity along one of the coordinate axes with respect to a set of opaque isothetic objects. Optimal algorithms to solve the visible points problems are presented. The algorithms are based on a new data structure called a covering tree. We illustrate the usefulness of the covering tree and the visible points problems by suggesting three applications involving isothetic objects. First, we present a hidden-line elimination algorithm for isothetic polyhedra which improves the previously best known algorithm for the same problem. Second, we describe an optimal query time algorithm for the three dimensional visibility searching problem. Finally, we show that whether or not two non-intersecting isothetic polyhedra with n vertices are separable by a single isothetic translation can be determined in O (nlogn) time and O(n) space. We consider the problem of internal line visibility of a simple polygon P with n vertices: determine whether or not there exists a line segment inside P from which every point inside P is visible. An O(nlogn) time and O(n) space algorithm for this problem is presented. Also we present a linear time algorithm for triangulating an internally line visible polygon.