Circular and parabolic visibility and their applications.

Abstract

In this thesis, the notions of circular and parabolic visibility are introduced as generalizations to linear visibility in the context of computational geometry. Fundamental visibility problems which have been solved with linear visibility are solved with circular and parabolic visibility. Additionally, applications beyond linear visibility are identified with circular or parabolic visibility. The circular arcs emanating from a fixed point are classified with respect to the edge of the simple polygon that they hit. By representing these circular visibility arcs by their corresponding centers, a plane partition is obtained. With the ability to compute such a plane partition, the region inside a simple polygon, which is circularly visible to a point or an edge, is computed accordingly. Such a partition is also computed with respect to a point inside a non-simple polygon. Similarly, the classification of the parabolic arcs with respect to the edge of a simple polygon the arcs hit is also achieved with a plane partition, in that the visibility parabolas are represented by their corresponding foci. Applications in the areas of robot motion planning and process modeling are discussed. Circular visibility is utilized to characterize robot motion planning, where the trajectory of the motion of a robot is characterized with circular arcs. Three problems, including the rotational separability problem, the minimum circular link path problem, and rotary joint positioning problem, are formulated. Parabolic visibility is utilized to characterize the chemical vapor deposition process, in which the trajectory of the motion of the deposited chemical is characterized with parabolic arcs. The amount of chemicals a surface point receives is solved as a point parabolic visibility problem.