Dynamic maintenance of view of points in three dimensional euclidean space

Abstract

A continuous change of relative positions of a set of points is perceived by a human observer only discretely. The reflection of a significant change in visibility in 3-dimensional Euclidean space in the perceived picture is called the change of view. The objective of this research is to define the term view and to provide necessary data structures and algorithms to maintain it dynamically. To determine the mentioned significant change in visibility, it is important to detect the presence of empty circle. So, to get the efficient query time for detecting the emptiness of a circle, we reveal some important properties of Gabriel graph. The main achievements of this thesis are a suitable data structure and efficient algorithms for maintaining the view dynamically with responsiveness O(M logM) and efficiency O(M log (M) s(n2)) where M is the degree of the moving vertex in the Delaunay graph and s(n) is the maximum length Davenport-Schinzel sequence of n symbols with order s. In fact, the growth of M logM is very low because M is an amortized constant.