1 files changed, 181 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/xelatex/yazd-thesis/chapter4.tex b/Master/texmf-dist/doc/xelatex/yazd-thesis/chapter4.tex
new file mode 100644
index 00000000000..2b46dbc9407
--- /dev/null
+++ b/Master/texmf-dist/doc/xelatex/yazd-thesis/chapter4.tex
@@ -0,0 +1,181 @@
+\chapter{ نمونه‌ای از یک فصل}
+\section{مدل‌های حرکت}\label{sec-model-motion}
+بسته به کاربرد، حرکت مجموعه نقاط در فضای دلخواه از راه‌های مختلف نمایش داده می‌شود. حرکت می‌تواند به صورت صریح با توابع چندجمله‌ای، به صورت ضمنی با معادلات دیفرانسیلی، یا به صورت آماری با مدل‌های احتمالی نمایش داده شود. همان‌طورکه بعداً دیده خواهد شد، در مسائل وابسته به حرکت که نقاط مسئله به‌طور پیوسته در حال حرکت هستند، لازم است تا وضعیت نقاط در هر زمان با مجموعه‌ای از شرط‌های جبری مشخص شود. علاوه بر این نیاز است تا مسیر حرکت نقاط به‌گونه‌ای تعریف شود که تعداد دفعاتی که یک شرط جبری ممکن است نامعتبر ‌شود ثابت باشد. بدین منظور در این پایان‌نامه، فرض می‌شود که مسیر حرکت نقاط در صفحه به صورت  \textbf{حرکت‌های شبه‌جبری}\LTRfootnote{Pseudo algebraic motions} است. برای تعریف این نوع حرکت‌ها لازم است توابع شبه‌جبری تعریف شوند، که از تعریف زانگ\LTRfootnote{Zhang} مطرح شده در
+ %\cite{z-kmps-00} 
+ استفاده می‌شود. 
+
+\begin{definition}\label{def-psdo-algb-func}
+توابع پیوسته‌ی یک متغیره‌ی $f_{1}(x), f_{2}(x), ... , f_{m}(x)$، توابع شبه‌جبری از درجه‌ی حداکثر $s$ هستند، هرگاه برای هر تابع چندجمله‌ای $m$ متغیره‌ی $g$  از درجه‌ی $s_{1}$،  تابع  $$h(x) = g(f_{1}(x), f_{2}(x), ... , f_{m}(x))$$  متحد صفر باشد یا حداکثر $s \times s_{1}$  ریشه داشته باشد.
+ \end{definition}
+  برای نمونه، توابع چندجمله‌ای یا منطقی با درجه‌ی ثابت توابع شبه‌جبری هستند. یک مجموعه از نقاط دارای حرکت‌های شبه‌جبری از زمان هستند هرگاه مسیر حرکت آن‌ها با توابع شبه‌جبری از زمان توصیف شود. در ادامه، تعریف \ref{def-psdo-algb-func} با شرح یک مثال توضیح داده می‌شود. 
+ 
+مسئله‌ی یک بعدی زیر که ترتیب $n$ نقطه‌ی در حال حرکت روی محور $x$ ها را گزارش می‌کند، درنظر بگیرید. هر نقطه‌ی $p_{i}$  دارای مسیر حرکت پیوسته‌ای از زمان است که با $f_{i}(t)$  نشان داده می‌شود و $t$ به زمان اشاره می‌کند. مقدار هر نقطه‌ی $p_{i}$  در زمان $t$، یعنی مولفه‌ی $x$ نقطه، با $v_{i}(t)$ نشان داده می‌شود. فرض کنید مجموعه توابع حرکت نقاط، یعنی $f_{1}(t), f_{2}(t), ... ، f_{n}(t)$،  توابع شبه‌جبری از درجه‌ی $s$ باشند و شرط‌های جبری برای تعیین موقعیت نقاط متحرک از نوع مقایسه تعریف شوند. اگر برای نشان دادن ترتیب هر دو نقطه‌ی متوالی $p_{i}$ و $p_{j}$ روی محور $x$ در زمان $t$، به‌طوری‌که $ v_{j}(t) > v_{i}(t)$ باشد، از شرط جبری $ v_{j}(t) - v_{i}(t) > 0$  استفاده شود، آنگاه با توجه به تعریف \mbox{\ref{def-psdo-algb-func}}، می‌توان تابع دو متغیره‌ی خطی $g(f_{j}, f_{i})(t) =  f_{j}(t) - f_{i}(t)$ (که طبق تعریف دارای $s_{1} = 1$ و $m = 2$ است)، را به عنوان تابع $h(t)$ درنظر گرفت و به این نتیجه رسید که تابع $h(t) = g(f_{j}, f_{i})(t)$ یا متحد صفر است یا دارای حداکثر $s \times 1$  ریشه است. این بدان معنی است که شرط جبری $ v_{j}(t) - v_{i}(t) > 0$ با گذشت زمان حداکثر به تعداد $s$ بار صفر می‌شود و متعاقباً تغییر علامت می‌دهد (تغییر ترتیب نقاط).
+ 
+در تحلیل مسائلی که بعداً مطرح خواهند شد، بسیار اهمیت دارد که تعداد دفعاتی که شرط جبری مربوط به یک نقطه با گذشت زمان صفر می‌شود ثابت باشد. از آن‌جایی که در بیش‌تر مسائل شرط‌های جبری که برای تعیین وضعیت نقاط معرفی می‌شوند، چندجمله‌ای‌هایی از درجه‌ی کم، تعریف شده روی یک تعداد ثابت از نقاط هستند، فرض شبه‌جبری بودن حرکت نقاط کافی است تا برقراری این موضوع را تضمین کند. برای نمونه، در مثال بالا شرط‌های جبری (مقایسه‌ی دو مقدار) از درجه‌ی یک و تعریف شده روی دو نقطه هستند، بنابراین با فرض شبه‌جبری بودن حرکت نقاط، شرط جبری مربوط به یک نقطه همان تابع $g$ مطرح شده در تعریف \ref{def-psdo-algb-func} می‌شود که حداکثر به تعداد $s \times 1$  بار صفر خواهد شد ( $s$ یک عدد ثابت که درجه‌ی توابع شبه‌جبری حرکت را نشان می‌دهد). 
+
+ \section{دنباله‌ی داونپورت-شینزل}\label{sec-DS-sequence}
+ \begin{definition}
+\label{def-DS-sequ}
+یک $(n, s)$ دنباله‌ی داونپورت-شینزل\LTRfootnote{Davenport-Schinzel sequence}، که $n$ و $s$ اعداد صحیح مثبت هستند، یک دنباله‌ی ساخته شده از $n$ نماد با این خواص است که هیچ دو نماد مجاور در دنباله یکسان نیستند و این‌که برای هر دو نماد مجزای $a$ و $b$  حداکثر $s$  تناوب از آن‌ها در دنباله وجود دارد.
+ \end{definition}
+در تعریف بالا، منظور از تناوب $a$ و $b$ این است که نماد $b$ بعد از نماد $a$ و نماد $a$ بعد از نماد $b$ در دنباله ظاهر شود، ولی نه الزاماً مجاور به هم (کنار هم). مثلاً دنباله‌ی زیر، تشکیل شده از نمادهای $a, b, c, d$ را در نظر بگیرید: $$\underline{a}c\underline{b}dbc\underline{a}cd
+\underline{b}\underline{a}dcdcadc\underline{b}$$ تعداد تناوب‌های $a$ و $b$ در دنباله، یعنی مجموع تعداد دفعاتی که $b$ بعد از $a$  و $a$ بعد از $b$ در دنباله ظاهر شده است، برابر با 5 است. با توجه به تعریف $(n, s)$ دنباله‌ی داونپورت-شینزل، می‌توان دریافت که با یک $n$ و $s$ معلوم (داده شده)، بسته به مقدارهای $n$ و $s$،  دنباله‌‌های داونپورت-شینزل متعددی می‌توان یافت، اما همگی دارای طول‌های متناهی هستند؛ زیرا با توجه به تعریف، امکان وجود دو نماد مجاور یکسان در دنباله نیست و نیز تعداد تناوب‌های هر دو نماد مجزا در دنباله به تعداد حداکثر $s$ محدود شده است. مثلاً برای $n = 3$ و $s = 2$ و نمادهای $a, b, c$،  طول  $(3, 2)$ دنباله‌های داونپورت-شینزل ممکن، حداکثر 5 است؛ زیرا هر دنباله با طول 6 یا بیش‌تر متشکل از این نمادها، یا حداقل برای یک جفت نماد مجزا دارای بیش از 2 تناوب خواهد بود یا دو نماد مجاور یکسان خواهد داشت و در نتیجه، شرایط تعریف یک $(3, 2)$ دنباله‌ی داونپورت-شینزل را نخواهد داشت، به عنوان مثال دنباله‌ی $abcbab$ که 3 تناوب از $a$ و $b$ را دارد. بنابراین طول طولانی‌ترین $(n, s)$ دنباله‌ی داونپورت-شینزل قابل تعریف خواهد بود 
+و با $\lambda_{s}(n)$ نشان داده می‌شود. در ادامه به بیان اهمیت و کاربرد این دنباله‌ها در تحلیل مسائلی‌ مهم در هندسه‌ی محاسباتی پرداخته می‌شود.
+
+اگر $\rbrace$ $f_{i}$ $ \lbrace$ $\cal F =$
+  یک مجموعه از توابع باشد،  \textbf{ پوشش پایینی}\LTRfootnote{Lower envelope}  برای مجموعه $\cal F$  برابر تابع $\min f_{i}(x)$ است که با  $\Gamma(\cal F)$ نشان داده می‌شود.  به طور مشابه  $\max f_{i}(x)$ به عنوان \textbf{پوشش بالایی}\LTRfootnote{Upper envelope}  تعریف می‌شود. پیچیدگی $\Gamma(\cal F)$ نیز برابر با تعداد دفعاتی که تابع موجود در $\Gamma(\cal F)$ عوض می‌شود، یعنی تعداد نقاط شکست $\Gamma(\cal F)$ تعریف می‌شود. 
+
+\begin{figure}[h]
+\begin{center}
+\includegraphics[width=0.5\textwidth]{DSsequence}
+\end{center}
+\caption{پوشش پایینی یک مجموعه از توابع متناظر با دنباله‌ای از نمادها}
+\label{fig-DSsequence}
+\end{figure}
+اگر $\cal F$ مجموعه‌ای از $n$ تابع چندجمله‌ای با درجه‌ی $s$ باشد. با توجه به این‌که هر دو تابع چندجمله‌ای از درجه‌ی $s$ حداکثر در $s$ نقطه با یکدیگر برخورد می‌کنند (این بدان معنی است که حداکثر $s$ تناوب از هر دو تابع مجزا از $\cal F$  در $\Gamma(\cal F)$ وجود خواهد داشت) و نیز وجود دو تابع یکسان مجاور به هم در $\Gamma(\cal F)$ هم امکان ندارد، به‌راحتی می‌توان نتیجه گرفت که $\Gamma(\cal F)$ متناظر با یک $(n, s)$ دنباله‌ی داونپورت-شینزل است و پیچیدگی آن نیز، برابر با طول دنباله‌ی داونپورت-شینزل متناظر با آن خواهد شد. شکل \ref{fig-DSsequence} را ببینید. پس می‌توان گفت که پیچیدگی $\Gamma(\cal F)$ از مرتبه‌ی $O(\lambda_{s}(n))$ است. تمام نتایج به‌طور مشابه برای پیچیدگی پوشش بالایی نیز برقرار است. اگر دامنه‌ی تعریف $\Gamma(\cal F)$ در نظر گرفته شود و هر تابع چندجمله‌ای از $\cal F$  روی قسمتی از این دامنه (یک بازه مشخص از دامنه) تعریف شود، یعنی نمودار هر تابع تکه‌ای از نمودار آن تابع با دامنه نامحدود باشد، آنگاه پیچیدگی $ \Gamma(\cal F)$ برابر $O(\lambda_{s+2}(n))$ می‌شود \cite{sp-dssga-95}.
+برای یک ثابت $s\geq 3$، $\lambda_{s}(n)$ یک تابع ابرخطی است اما خیلی آهسته رشد می‌کند. در ادامه قضیه‌ای بیان می‌شود که فرمول‌های مربوط به محاسبه  $\lambda_{s}(n)$ را بیان می‌کند. تابع $\alpha(n)$  به معکوس تابع آکرمان\LTRfootnote{Ackermann function} اشاره می‌کند \cite{sp-dssga-95}.
+
+\endinput
+\begin{theorem}\label{theo-DS-sequ}
+پیچیدگی پوشش پایینی (یا بالایی) یک مجموعه از $n$  تابع چندجمله‌ای با درجه $s$ برابر $O(\lambda_{s}(n))$ است، که $\lambda_{s}(n)$ در روابط زیر صدق می‌کند.
+
+$$\begin{array}{l l l l l}
+\lambda_{1}(n)  = n \\ \\
+\lambda_{2}(n)  = 2n - 1 \\ \\
+\lambda_{3}(n)  = \Theta(n\alpha(n)) \\ \\
+ \lambda_{s}(n)  \leq n2^{{(1+o(1))\alpha(n)}^{\frac{s - 2}{2}}} & $  باشد، زوج $n$اگر $\\ \\
+\lambda_{s}(n)  \leq n2^{{(1+o(1))\alpha(n)}^{\frac{s - 2}{2}}\log \alpha(n)} 
+ & $  باشد، فرد $n$اگر $ \end{array}$$
+\end{theorem}
+از آن جایی که $\alpha(n)$ تابعی است که بی‌نهایت آهسته رشد می‌کند (تقریبا برای مقادیر عملی و منطقاً بزرگ $n$ مقدار ثابت است)، بنابراین برای یک مقدار ثابت $s$، $\lambda_{s}(n)$ تقریبا خطی از $n$  است.   
+%%%%%%%%%%%%%%%%%%%%%
+ %%%%%%%%%%%%%%%%%%%
+\section{پوشش‌های هندسی روی مجموعه نقاط}\label{sec-t-spann}
+\subsection{شبکه‌های هندسی}
+مجموعه‌ی $P$ شامل $n$ نقطه در فضای $\mathbb{R}^d$ را درنظر بگیرید، یک \textbf{شبکه‌ی متصل‌کننده‌ی نقاط} $P$\LTRfootnote{A network connecting the points of P}، یک گراف ${\cal G} = (P, E)$ با مجموعه رأس‌های $P$ و مجموعه یال‌های $E \subseteq P\times P$  است، به‌طوری‌که هر دو نقطه‌ی $p, q \in P$ با یک مسیر در $\cal G$ به‌هم متصل می‌شوند. یک \textbf{شبکه‌ی هندسی}\LTRfootnote{Geometric network} یا یک \textbf{گراف اقلیدسی}\LTRfootnote{Euclidean graph}، یک گراف وزن‌دار ${\cal G}$ است که رأس‌ها متناظر با نقاط در فضای اقلیدسی و وزن روی یال‌ها متناظر با فاصله‌‌ی اقلیدسی بین نقاط انتهایی آن یال است. شبکه‌های هندسی در واقع تعداد زیادی از شبکه‌های حقیقی موجود، مانند شبکه راه‌ها، شبکه مخابرات و غیره را مدل می‌کنند.
+%\nocite{ns-gsn-07}
+
+برای طراحی یک شبکه برای مجموعه‌ی مشخصی از نقاط، چندین معیار کیفی در نظر گرفته می‌شود. در زیر تعدادی از مهم‌ترین معیارهای کیفی برای ارزیابی شبکه‌های هندسی بیان شده است.
+ \begin{enumerate}
+\item
+\textbf{اندازه}\LTRfootnote{Size}، به‌عنوان تعداد یال‌های شبکه تعریف می‌شود. در حالت کلی ترجیح داده می‌شود که شبکه‌ها تا جای ممکن اندازه‌ی کوچکی (خطی از تعداد نقاط) داشته باشند. 
+\item
+\textbf{وزن}\LTRfootnote{Weight}، به‌عنوان مجموع وزن یال‌های شبکه تعریف می‌شود. ازآن‌جایی‌که هر شبکه باید تمام نقاط را به‌هم وصل کند، درنتیجه وزن آن از پایین با وزن درخت پوشای کمینه کران‌دار می‌شود. وزن یک معیار خوب برای سنجش هزینه‌ی ساخت شبکه است. بنابراین، اغلب شبکه‌هایی با وزن کم مورد نظر هستند.
+\item
+\textbf{ضریب کشش}\LTRfootnote{Stretch factor}یا \textbf{تاخیر}\LTRfootnote{Dilation}  برای دو نقطه‌ی داده شده، برابر با نسبت کوتاه‌ترین مسیر (مسیر با وزن مینیمم) بین دو نقطه در شبکه، به فاصله‌ی آن دو نقطه بر اساس متر تعریف شده برای آن شبکه است (مثلاً این فاصله در متر اقلیدسی خط مستقیم متصل کننده‌ی دو نقطه است). ضریب کشش یک شبکه به‌عنوان بیش‌ترین ضریب کشش برای هر جفت از نقاط مجزا در شبکه تعریف می‌شود. در بسیاری از موارد، نیاز است که ضریب کشش شبکه با یک ثابت کوچک محدود شود (که حداقل باید یک باشد). شبکه‌ها با ضریب کشش حداکثر $t$، $t$-پوشش‌ها\LTRfootnote{t-Spanners} نامیده می‌شوند.
+\item
+\textbf{درجه}\LTRfootnote{Degree}،  بیش‌ترین تعداد یال‌های مجاور به هر نقطه در شبکه می‌باشد و اغلب نیاز است که با یک ثابت کوچک محدود شود. درجه‌ی محدود یک شبکه، به اندازه‌ی کوچک آن شبکه اشاره می‌کند، اما برعکس این مطلب لزوماً درست نیست.
+\end{enumerate}
+در حالت کلی، در زمان طراحی یک شبکه، آن‌چه که اهمیت زیادی دارد، اعمال ترکیبی از این معیارهای کیفی بر روی شبکه است و در زمان تحلیل شبکه نیز ویژگی‌های شبکه، نسبت به این معیارها سنجیده می‌شود. یکی از مسائل مهم در این زمینه، مطالعه‌ی شبکه‌هایی با ضریب کشش کم است (در ترکیب با دیگر ویژگی‌ها). ازجمله، در بسیاری از کاربردها مانند شبکه‌ی راه‌ها لازم است یک ارتباط سریع (مستقیم) بین هر جفت از نقاط در $P$ برقرار باشد (یعنی شبکه یک گراف کامل باشد) ولی این نیاز به خاطر هزینه‌های بالا، قابل اجرا شدن نیست. بنابراین نیاز به مطالعه‌ی شبکه‌هایی با ضریب کشش کم، منجر به شکل‌گیری مفهوم پوشش‌های هندسی می‌شود. این پوشش‌ها در واقع یک ساختار برای شبکه‌ها، زمانی که ارتباطات کوتاه بین نقاط اهمیت دارند را فراهم می‌کنند.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{$t$-پوشش‌های هندسی}
+ \begin{definition}
+\label{def-t-spanner}
+مجموعه‌ی $P$ شامل $n$ نقطه در فضای $\mathbb{R}^d$ و $t \geq 1$ را یک عدد حقیقی درنظر بگیرید. یک $t$-\textbf{پوشش}\LTRfootnote{t-spanner} برای $P$، یک گراف بدون ‌جهت $\cal G$ با مجموعه رأس‌های $P$  است، به‌طوری‌که کوتاه‌ترین مسیر بین هر دو نقطه‌ی $p$ و $q$ از $P$،  در $\cal G$ که با نماد $d_{\cal G}(p, q)$ نشان داده می‌شود، این شرط را داشته باشد:
+$$d_{\cal G}(p, q) \leq t \cdot ||pq||.$$ هر مسیری که این شرط را برآورده سازد یک $t$-\textbf{مسیر}\LTRfootnote{t-path} بین $p$ و $q$ نامیده می‌شود.
+\end{definition}
+ برای هر عدد حقیقی $t^{'}$ که $t^{'} > t$ است، اگر $\cal G$ یک $t$-پوشش برای مجموعه نقاط $P$  باشد، بدیهی است که $\cal G$ یک $t^{'}$-پوشش نیز برای $P$ است. این، منجر به تعریف زیر می‌شود:
+ \begin{definition}[\textbf{ضریب کشش}]
+\label{def-strtch-factor}
+مجموعه‌ی $P$ شامل $n$ نقطه در فضای $\mathbb{R}^d$ و $\cal G$ را یک گراف اقلیدسی با مجموعه رأس‌های $P$ درنظر بگیرید. ضریب کشش $\cal G$، کوچک‌ترین عدد حقیقی $t$ است به‌طوری‌که $\cal G$ یک $t$-پوشش از $P$ باشد.
+\end{definition}
+گراف کامل یک 1-پوشش است، اما تعداد مربعی یال دارد. درحقیقت، اگر فرض شود که هیچ سه نقطه‌ای از $P$  روی یک خط قرار ندارند، سپس گراف کامل تنها 1-پوشش برای $P$ است. بنابراین، در حالت کلی $t$-پوشش‌ها برای $t$ های بزرگ‌تر از یک بررسی می‌شوند. اما از آن‌جایی که در بسیاری از کاربردها، پوشش‌هایی با ارتباطات سریع (ضریب کشش کم) مورد نیاز هستند. بنابراین پوشش‌هایی با ضریب کشش نزدیک به یک، مورد مطالعه قرار می‌گیرند، یعنی $t = 1 + \varepsilon$،  برای مقادیر $\varepsilon$ مثبت و کوچک ($0 < \varepsilon < 1$). به این ترتیب، می‌توان با انتخاب مقادیر خیلی کوچک برای $\varepsilon$، مقدار $t$ را به یک نزدیک کرد، یعنی $t$-پوشش را به یک $1$-پوشش (گراف کامل) نزدیک کرد.
+ %%%%%%%%%%%%%%%%%%%%%%%%%
+
+ \section{ یک پوشش هندسی وابسته به حرکت در صفحه}
+در این فصل یک $1 + \varepsilon$-پوشش ساده با اندازه‌ی خطی، برای یک مجموعه از $n$ نقطه در صفحه معرفی می‌شود. این پوشش زمانی‌که نقاط آن حرکت می‌کنند، می‌تواند به‌صورتی کارا نگهداری شود. فرض می‌شود که مسیر حرکت نقاط با توابع شبه‌جبری از درجه‌ی حداکثر $s$ توصیف می‌شوند (بخش \ref{sec-model-motion} را ببینید). لازم به ذکر است که مطالب این فصل بر اساس مقاله‌ی آبام\LTRfootnote{Abam} و همکارانش \cite{abg-seks-10} تنظیم شده است. \section{کارهای مرتبط}
+یک $1 + \varepsilon$-پوشش را درنظر بگیرید. برای جزئیات بیش‌تر در مورد پوشش‌ها می‌توانید بخش \ref{sec-t-spann} را ببینید. هنگامی که نقاط پوشش دارای حرکت پیوسته‌ای از زمان باشند، پوشش به‌طور پیوسته از زمان تغییر می‌کند، اما تنها در لحظه‌های مشخصی نیاز به به‌روزرسانی خواهد داشت، تا همچنان در تمام زمان‌ها یک $1 + \varepsilon$-پوشش باقی بماند. در فصل 2 بیان شد که این لحظات رویداد نامیده می‌شوند. از آن‌جایی که کارایی و پاسخ‌گویی، از مهم‌ترین معیارها برای ارزیابی کیفیت ساختارهای وابسته به حرکت هستند، هدف، طراحی پوششی است که تعداد رویدادها و نیز زمان پاسخ‌گویی آن، کم باشد. همان‌طورکه در فصل 2 بیان شد، در حالت ایده‌ال، تعداد رویدادها باید نزدیک به کم‌ترین تعداد رویدادهایی که برای نگهداری ساختار لازم است باشد. برای پوشش‌ها، این بدین معنی است که تعداد رویدادها باید $O(n^{2})$ باشد؛ زیرا مجموعه‌های $n$ تایی از نقاط که به‌صورت خطی در صفحه حرکت می‌کنند وجود دارند، که برای هر $1 + \varepsilon$-پوشش باید $\Omega(n^{2}/(1 + \varepsilon)^{2})$ رویداد پردازش شود.
+% \cite{ggn-dsa-06}. 
+زمان پاسخ‌گویی نیز در حالت ایده‌ال باید چندلگاریتمی باشد.
+
+\subsection{تحلیل ضریب کشش و اندازه‌ی پوشش}  \label{subsec-span-ratio}
+در این زیربخش ثابت خواهد ‌شد که اگر زاویه‌های $\phi$ و $\varphi$ به‌گونه‌ای انتخاب شوند که شرط‌های 
+%\begin{latin}
+\begin{equation}\label{eq-rd-first}
+(\cos \phi - \sin \phi) \geq 1/(1 + \varepsilon) 
+\end{equation} 
+%\end{latin}
+و
+ \begin{equation}\label{eq-rd-sec}(\sin(\phi/2)/\sin(\varphi/2)) \geq 1 + 2/\varepsilon \end{equation}
+ برقرار باشند، آنگاه ${\cal DDS}(P)$ یک $1 + \varepsilon$-پوشش برای مجموعه نقاط $P$ خواهد بود. این شرط‌ها می‌توانند با تنظیم زوایای $\phi$ و $\varphi$ به‌صورت  $ \phi = \arcsin \frac{\varepsilon}{2(1+\varepsilon)}$ و $ \varphi = 2\arcsin \frac{\varepsilon^{2}}{4(1+\varepsilon)(2+\varepsilon)}$  به‌دست آیند. همواره فرض می‌شود که $\varphi <\phi$.  
+\begin{observation}
+\label{obsr-phi}
+اگر $ \phi = \arcsin \frac{\varepsilon}{2(1+\varepsilon)}$ برقرار باشد آنگاه $0 < \phi < \dfrac{\pi}{6}$.
+\end{observation}
+\begin{proof}
+از آن‌جایی‌که، $\dfrac{\varepsilon}{2(1+\varepsilon)} < \dfrac{1}{2}$  و تابع $\arcsin$ در بازه $ (0, \pi/2)$ یک تابع صعودی است، بنابراین،
+ $$0 < \phi = \arcsin \frac{\varepsilon}{2(1+\varepsilon)} < \arcsin \frac{1}{2} = \dfrac{\pi}{6}.$$
+\end{proof}
+\begin{observation}
+\label{obsr-angles}
+با انتخاب $ \phi = \arcsin \frac{\varepsilon}{2(1+\varepsilon)}$ و $\varphi = 2\arcsin \frac{\varepsilon^{2}}{4(1+\varepsilon)(2+\varepsilon)}$ دو شرط \ref{eq-rd-first} و \ref{eq-rd-sec} برقرار است.
+\end{observation}
+\begin{proof}
+قسمت اول اثبات: با توجه به مشاهده‌ی \ref{obsr-phi}، رابطه‌ی 
+$0 < \phi < \dfrac{\pi}{6}$ برقرار است، بنابراین رابطه‌ی 
+$\cos \phi \geq 1-\sin \phi$ نیز برقرار خواهد بود و شرط 
+\ref{eq-rd-first} به این صورت اثبات می‌شود:
+\begin{LTR}
+\begin{center}
+\begin{tabular}{rll} 
+$\phi$  & $=$ & $\arcsin \frac{\varepsilon}{2(1 + \varepsilon)}$\\ \\
+$\sin \phi $  & $=$ & $\dfrac{\varepsilon}{2(1 + \varepsilon)}$\\ \\
+$2\sin \phi- 1$ & $=$ & $\dfrac{\varepsilon}{1 + \varepsilon} - 1$\\  \\
+$1 - 2\sin \phi$ & $=$ & $\dfrac{1}{1 + \varepsilon}$
+\end{tabular}
+\end{center}
+\end{LTR}
+\begin{LTR}
+\begin{center}
+\begin{tabular}{rll} 
+$1- \sin \phi-\sin \phi$ & $=$ & $\dfrac{\varepsilon}{1 + \varepsilon}$\\  \\
+$\cos \phi - \sin \phi$ & $\geq$ & $\dfrac{1}{1 + \varepsilon}.$
+\end{tabular}
+\end{center}
+\end{LTR}
+قسمت دوم اثبات: از مشاهده‌ی \ref{obsr-phi}، رابطه‌ی  
+\mbox{$\dfrac{1}{2} < \cos(\phi/2) < 1$} و از قسمت اول اثبات، 
+رابطه‌ی $\sin \phi = \dfrac{\varepsilon}{2(1 + \varepsilon)}$ 
+برقرار است. با توجه به این روابط و نیز رابطه‌ی مثلثاتی \linebreak $\sin \phi = 2\sin(\phi/2) \cos(\phi/2)$، شرط \ref{eq-rd-sec} به این صورت اثبات می‌شود:
+\begin{center}
+\begin{LTR}
+\begin{tabular}{rll}
+$\varphi$ & $=$ & $2\arcsin \frac{\varepsilon^{2}}{4(\varepsilon + 2)(1 + \varepsilon)}$ \\ \\
+$\sin(\varphi/2)$ & $=$ & $\dfrac{\varepsilon^{2}}{4(\varepsilon + 2)(1 + \varepsilon)}$ \\  \\
+$\sin(\varphi/2)\cos(\phi/2)$ & $\leq$ & $\dfrac{\varepsilon^{2}}{4(\varepsilon + 2)(1 + \varepsilon)}$ \\  \\
+$\dfrac{1}{\sin(\varphi/2)\cos(\phi/2)}$ & $\geq$ & $\dfrac{4(\varepsilon + 2)(1 + \varepsilon)}{\varepsilon^{2}}$ \\  \\
+$\dfrac{\dfrac{\varepsilon}{2(1 + \varepsilon)}}{\sin(\varphi/2)\cos(\phi/2)}$ & $\geq$ & $\dfrac{2(\varepsilon + 2)}{\varepsilon}$ \\  \\
+$\dfrac{\sin\phi}{2\sin(\varphi/2)\cos(\phi/2)}$ & $\geq$ & $\dfrac{\varepsilon + 2}{\varepsilon}$ \\  \\
+$\dfrac{\sin(\phi/2)}{\sin(\varphi/2)}$ & $\geq$ & $1 + 2/\varepsilon.$
+\end{tabular}
+\end{LTR}
+\end{center}
+\end{proof}
+
+\begin{lemma}
+پیچیدگی پوشش پایینی (یا بالایی) یک مجموعه از $n$  تابع چندجمله‌ای با درجه $s$ برابر $O(\lambda_{s}(n))$ است، که $\lambda_{s}(n)$ در روابط زیر صدق می‌کند.
+
+$$\begin{array}{l l l l l}
+\lambda_{1}(n)  = n \\ \\
+\lambda_{2}(n)  = 2n - 1 \\ \\
+\lambda_{3}(n)  = \Theta(n\alpha(n)) \\ \\
+ \lambda_{s}(n)  \leq n2^{{(1+o(1))\alpha(n)}^{\frac{s - 2}{2}}} & $  باشد، زوج $n$اگر $\\ \\
+\lambda_{s}(n)  \leq n2^{{(1+o(1))\alpha(n)}^{\frac{s - 2}{2}}\log \alpha(n)} 
+ & $  باشد، فرد $n$اگر $ \end{array}$$
+\end{lemma}
+
+\begin{example}
+نمونه مثال
+\end{example}
+\begin{proposition}
+نمونه گزاره
+\end{proposition}
+\begin{corollary}
+نمونه نتیجه
+\end{corollary}
+
+\begin{remark}
+نمونه ملاحظه
+\end{remark}
+
+