Visibility in reflective environments.

Abstract

The primary goal of this thesis is to establish fundamental algorithms for visibility in reflective environments and to propose a unified framework for locating remote objects without direct visibility. This research covers two major topics. First, we develop algorithms for visibility under reflections and propose its applications in both two and three dimensions. Visibility is considered as a piecewise-linear path that follows Snell's law of reflection, whereas traditional research concerns only the direct line-of-sight. Algorithms presented in this research are generalizations and extensions of M. E. Wang's research in two-dimensional reflective visibility[59]. Second, we introduce complex coefficients to quaternions and establish a unified formula to represent both reflections and rotation. We show that two complex quaternions (with 6 degrees of freedom and one extra bit) are sufficient to carry the information for any two-dimensional or threedimensional congruent transformations. These two topics have been rarely studied even though potential applications abound, such as ray-tracing, prediction of indoor radio propagation, computer animation, virtual reality, and locating remote objects. A data structure called <italic>Forward Bounce Tree</italic> (FBT) is employed to store visibility information in a reflective environment with respect to an omnidirectional source. <italic>O</italic>(<italic>b</italic><super> 2</super>) and <italic>O</italic>(<italic>b</italic><super>3</super>) space complexities, where <italic>b</italic> is the number of reflections, are established for special two-dimensional and three-dimensional honeycomb compatible environments, respectively. Sub-exponential growth rates are obtained empirically for three-dimensional polyhedral environments with regular faces. From the application point of view, while technologies such as the <italic> Global Positioning System</italic> are available, locating objects in a closed environment (such as libraries, factories, warehouses) without the benefit of direct lines-of-sight, remains rarely studied. A <italic> Beaconing Bar Code</italic> software system is implemented in two dimensions to locate remote objects without direct visibility. A hardware prototype of the Beaconing Bar Code system and receiver allocation issues are discussed. Heuristic algorithms are given for reducing the number of receivers yet maintaining locatability. Algorithms are extended to three-dimensional space for constructing FBTs, for testing reflective visibility, for finding the shortest path in reflective environments with obstacles, for locating remote objects, and for receiver arrangements.