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.
