blob: af1c11dad660af66212e73354bfdc141e16738e3 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
% در این فایل، عنوان پایاننامه، مشخصات خود و چکیده پایاننامه را به انگلیسی وارد کنید.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{latin}
\latinfaculty{Faculty of Sciences}
\latindepartment{Department of Mathematical Sciences}
\latinfield{Communications (System)}
\latintitle{English Title of the Thesis}
\firstlatinsupervisor{First Supervisor}
\secondlatinsupervisor{Second Supervisor}
\firstlatinadvisor{First Advisor}
\secondlatinadvisor{Second Advisor}
\latinname{Nasser}
\latinsurname{Dehghan}
\latinthesisdate{January 2015}
\enabstract{
\subsection*{Abstract}
\thispagestyle{empty}
\baselineskip=1cm
In this thesis, we study $1 + \varepsilon$-spanners for a set of $n$ points in the plane and in
d-dimensional Euclidean space that can be maintained efficiently as the points move. The
kinetic spanner in the plane has size $O(n/\varepsilon^{2})$. Assuming the trajectories of
the points can be described by polynomials whose degrees are at most $s$,
the number of events is $O(n^{2}\beta(n))$ ($\beta(n)$ grows slower than logarithmic functions),
and at each event the spanner can be updated in $O(1)$ time. The kinetic spanner in $\mathbb{R}^{d}$ has
size $O(n/\varepsilon^{d-1})$ and maximum degree $O(\log^{d} n)$. Assuming that the
trajectories of the points can be described by bounded-degree polynomials, the number of
events is $O(n^{2}/\varepsilon^{d-1})$, and using a supporting data
structure of size $O((n/\varepsilon^{d-1})\log^{d} n)$, we can handle events in
time $O(\log^{d+1} n)$. Moreover, the spanner can be updated in time $O(\log n/\varepsilon^{d-1})$ if
the flight plan of a point changes. These spanners are the first kinetic spanners whose performance does not depend on
the spread of the point set.
}
\latinyazdtitle
\end{latin}
|
