\chapter{•‰ƒ‰‘¢ù¨‰‘¥ı ó‰Ú‰¤ş‰µ‰İ \label{implement}} ¢¤ ş‰ß ê‰Ê‰Û —‰®‰ƒ‰½‰‘—‰ü ¢¤“‰‘¤ùı •‰ƒ‰‘¢ù¨‰‘¥ı ó‰Ú‰¤ş‰µ‰Ş‰ü  ¢¤ “‰¿‰Ç \ref{alg} —‰È‰Âş‰¼ ª‰À ¡‰û‰ƒ‰İ ¢¢. õ‰µ‰ß õ‰Û ş‰ß “‰Â÷‰‘õ‰‚ ¢¤ •‰ƒ‰¨‰´ \ref{sourceA} õ‰Àù ¨‰´. ş‰ß “‰Â÷‰‘õ‰‚ ¥ ó‰Ú‰¤ş‰µ‰İ ê‰Ê‰Û \ref{alg} ¢¤ Ÿ‰‘ó‰´ õ‰½‰À’ ¨‰µ‰Ô‰‘¢ù õ‰ü‰À. 󉱉µ‰‚ “‰‚ ş‰ß ¢ó‰ƒ‰Û  ¨‰Î‰ ÷‰‘õ‰€‰Ñ‰İ õ‰·‰Ü‰¶“‰€‰Àı ª‰Àù ¢¤ Ÿ‰‘ó‰´ î‰Ü‰ü õ‰½‰À’ ÷‰ƒ‰Æ‰µ‰€‰À ø “‰€‰‘“‰Âş‰ß ş‰ß ó‰Ú‰¤ş‰µ‰İ “‰Âı öû‰‘ ¤ ÷‰Ş‰ü‰À, ì‰Æ‰Ş‰µ‰ü “‰‚ ó‰Ú‰¤ş‰µ‰İ ®‰‘ꉂ ª‰Àù ¨‰´  “‰‘ ¨‰µ‰Ô‰‘¢ù ¥ ö õ‰ü—‰ö “‰Âı û‰Â ¨‰Î‰¼ ÷‰‘õ‰€‰Ñ‰İ õ‰·‰Ü‰¶“‰€‰Àı ª‰Àùş‰ü ) õ‰ü—‰÷‰À 艃‰Âõ‰½‰À’ û‰İ “‰‘ª‰À( ‰‘ù—‰Âş‰ß õ‰Æ‰ƒ‰Â ¤ •‰ƒ‰À õ‰ü‰À; û‰Â ‰€‰À  ş‰ß ì‰Æ‰Ş‰´ ®‰‘ꉂ “‰Âı Ÿ‰‘ó‰´ è‰ƒ‰Âõ‰½‰À’, ¥ ¥õ‰‘ö ›‰Âı \InE{}$O(n^3)$\EnE{} “‰Â¡‰¤¢¤ ¨‰´ ø “‰€‰‘“‰Âş‰ß ‰À—‰Â ¥ ó‰Ú‰¤ş‰µ‰İ ¬‰Ü‰ü ¤‰‚ ª‰Àù ¢¤ “‰¿‰Ç \ref{alg} ¨‰´, øó‰ü ¢¤ õ‰Ö‰‘“‰Û •‰ƒ‰‘¢ù¨‰‘¥ı ö “‰‚ õ‰Â—‰° ¨‰‘¢ù—‰Â ¥ •‰ƒ‰‘¢ù¨‰‘¥ı ó‰Ú‰¤ş‰µ‰İ “‰¿‰Ç \ref{alg} ¢¤ Ÿ‰‘ó‰´ è‰ƒ‰Âõ‰½‰À’ ¨‰´ ø 䉅øù “‰Â ş‰ß ‰‘ù—‰Âş‰ß õ‰Æ‰ƒ‰Â “‰ƒ‰ß û‰Â ¢ø ÷‰Ö‰Î‰‚ş‰ü ¤ ÷‰ƒ‰Ã “‰‚ ¢¨‰´ õ‰üø¤¢. )ø ÷‰‚ ‰‘ù—‰Âş‰ß õ‰Æ‰ƒ‰Â ¥ ş‰× õ‰±‰À\hamze õ‰È‰¿‰É “‰‚ “‰Ö‰ƒ‰‚ı ¤‰§( “‰‘ —‰›‰‚ “‰‚ ş‰ß ¢„ş‰Û, ¨‰µ‰Ô‰‘¢ù ¥ ş‰ß ó‰Ú‰¤ş‰µ‰İ “‰‚ ›‰‘ı —‰ç‰ƒ‰ƒ‰Â ¤‰‚ ª‰Àù ¢¤ “‰¿‰Ç \ref{nonconvexsec} “‰Âı Ÿ‰‘ó‰´ ÷‰‘õ‰½‰À’ õ‰ã‰Ö‰ñ “‰‚ ÷‰Ñ‰Â õ‰ü¤¨‰À. ¢¤ ş‰ß ê‰Ê‰Û “‰µ‰À ¢¤ “‰¿‰Ç \ref{io} ê‰Âõ‰´ ø¤ø¢ı ø ¡‰Âø›‰ü “‰Â÷‰‘õ‰‚ ¤ —‰È‰Âş‰¼ ¡‰û‰ƒ‰İ î‰Â¢. •‰Å ¥ ö ¢¤ “‰¿‰Ç \ref{structure} ¨‰‘¡‰µ‰‘¤ î‰Ü‰ü “‰Â÷‰‘õ‰‚ ø õ‰‘›‰ñû‰‘ı õ‰¿‰µ‰Ü‰Ó ö õ‰¤¢ “‰Â¤¨‰ü ì‰Â¤ ¡‰û‰À ğ‰Âꉴ ø —‰“‰â õ‰ú‰İ “‰Â÷‰‘õ‰‚ õ‰ã‰Âê‰ü ¡‰û‰€‰À ª‰À. ¨‰³‰Å ¢¤ “‰¿‰Ç \ref{datastr} ¢¤“‰‘¤ùı ¨‰‘¡‰µ‰Ş‰‘ö ¢¢ùû‰‘ı õ‰ú‰Ş‰ü  ¢¤ “‰Â÷‰‘õ‰‚ ¨‰µ‰Ô‰‘¢ù ª‰Àù ¨‰´ —‰®‰ƒ‰¼ õ‰ü¢û‰ƒ‰İ. “‰¿‰Ç \ref{difficulty} “‰‚ “‰Â¤¨‰ü õ‰È‰Ø‰…– õ‰›‰¢ ¢¤ •‰ƒ‰‘¢ù¨‰‘¥ı ş‰ß ó‰Ú‰¤ş‰µ‰İ ¡‰û‰À •‰Â¢¡‰´. ¢¤ “‰¿‰Ç \ref{test} ¤ø©û‰‘ş‰ü “‰Âı —‰Æ‰´ “‰Â÷‰‘õ‰‚ •‰ƒ‰È‰€‰ú‰‘¢ ¡‰û‰ƒ‰İ î‰Â¢. ¢¤ ÷‰µ‰ú‰‘ ¢¤ “‰¿‰Çû‰‘ı \ref{sample} ø \ref{runningtime} ÷‰Ş‰÷‰‚û‰‘ş‰ü ¥ ¡‰Âø›‰ü “‰Â÷‰‘õ‰‚ ¤ ¡‰û‰ƒ‰İ ¢ş‰À ø ¥õ‰‘ö ›‰Âı “‰Â÷‰‘õ‰‚ ¤ “‰‚ ω¤ õ‰µ‰¨‰Í “‰Â¤¨‰ü ¡‰û‰ƒ‰İ î‰Â¢. \section{\label{io} ø¤ø¢ı ø ¡‰Âø›‰ü} ø¤ø¢ı “‰Â÷‰‘õ‰‚ ¥ ꉑş‰Ü‰ü ¨‰´  ÷‰‘ô ö “‰‚ 䉀‰ö øó‰ƒ‰ß •‰‘¤õ‰µ‰Â ¡‰Í ¢¨‰µ‰¤ )\InE{}Command Line\EnE{}( “‰‚ “‰Â÷‰‘õ‰‚ ¢¢ù õ‰üª‰¢. ş‰ß ꉑş‰Û ª‰‘õ‰Û õ‰È‰¿‰Ê‰‘– ş‰× ¨‰Î‰¼ ÷‰‘õ‰€‰Ñ‰İ õ‰·‰Ü‰¶“‰€‰Àı ª‰Àù ¨‰´. “‰Àş‰ß ¬‰¤–  ¢¤ ¡‰Í øñ —‰ã‰À¢ ÷‰Ö‰‘¯ )\InE{}$n$\EnE{}( ø ¨‰³‰Å —‰ã‰À¢ õ‰·‰Ü‰¶û‰‘ı õ‰›‰¢ ¢¤ \InE{}TIN\EnE{} )\InE{}$m$\EnE{}( ÷‰ª‰µ‰‚ ª‰Àù ¨‰´. •‰Å ¥ ö ¢¤ \InE{}$n$\EnE{} ¡‰Í “‰ã‰À ¢¤ û‰Â ¡‰Í ¨‰‚ ä‰À¢ Ÿ‰Ö‰ƒ‰Ö‰ü  ÷‰È‰‘ö¢û‰€‰Àùı õ‰¿‰µ‰Ê‰‘– ş‰Ø‰ü ¥ ÷‰Ö‰‘¯ )õ‰¿‰µ‰Ê‰‘– ¨‰‚ “‰ã‰Àı( ¨‰´ ÷‰ª‰µ‰‚ ª‰Àù ¨‰´. •‰Å ¥ ş‰ß ¡‰Î‰¯, ¢¤ \InE{}$m$\EnE{} ¡‰Í “‰ã‰À, ¢¤ û‰Â ¡‰Í ¨‰‚ ä‰À¢ ¬‰½‰ƒ‰¼  ÷‰È‰‘ö¢û‰€‰Àùı ª‰Ş‰‘¤ùı ¨‰‚ ¤\hamze § ş‰Ø‰ü ¥ õ‰·‰Ü‰¶û‰‘ û‰Æ‰µ‰€‰À ÷‰ª‰µ‰‚ ª‰Àù ¨‰´. 䉅øù “‰Â ş‰ß ¢¤ ¡‰Í ¡‰Â ꉑş‰Û ¢ø ä‰À¢ ÷‰ª‰µ‰‚ ª‰Àù ¨‰´  ª‰Ş‰‘¤ùı ¤‰§ õ‰±‰À\hamze ø õ‰Ö‰Ê‰À û‰Æ‰µ‰€‰À. “‰Âı õ‰·‰‘ñ ª‰Ø‰Û \ref{inputexample} ş‰× ÷‰Ş‰÷‰‚ ¥ ꉑş‰Û ø¤ø¢ı ø \InE{}TIN\EnE{} õ‰Â“‰¯ “‰‚ ö ¤ ÷‰È‰‘ö õ‰ü¢û‰À. ş‰ß \InE{}TIN\EnE{} ª‰‘õ‰Û 01 ¤\hamze § ø 11 õ‰·‰Ü‰¶ ¨‰´. \begin{figure} \english \hbox{ \hbox to 4cm{\vbox{ \input{infile} }} \input{inexamp} } \farsi \caption{\label{inputexample} ş‰× ÷‰Ş‰÷‰‚ ¥ ꉑş‰Û ø¤ø¢ı} \end{figure} \english\farsi ¡‰Âø›‰ü “‰Â÷‰‘õ‰‚ û‰İ ¢¤ ꉑş‰Û ø û‰İ “‰Â ¤øı ¬‰Ô‰½‰‚ı ÷‰Ş‰‘ş‰Ç ÷‰È‰‘ö ¢¢ù õ‰üª‰¢. ¨‰İ ꉑş‰Û ¡‰Âø›‰ü, •‰‘¤õ‰µ‰Â ¢øô ¡‰Í ¢¨‰µ‰¤ ¨‰´. ¢¤ ¨‰Î‰Â øñ ş‰ß ꉑş‰Û, —‰ã‰À¢ ÷‰Ö‰‘¯ ¤øı õ‰Æ‰ƒ‰Â )“‰‘ Ÿ‰µ‰Æ‰‘’ ÷‰Ö‰Î‰‚ı ª‰Âøá ø •‰‘ş‰‘ö( ø û‰Ş‰»‰€‰ƒ‰ß ωñ õ‰Æ‰ƒ‰Â ÷‰ª‰µ‰‚ ª‰Àù ¨‰´. ¢¤ ¡‰Íû‰‘ı “‰ã‰À, ¢¤ ¡‰Í \InE{}$i$\EnE{}ô, õ‰¿‰µ‰Ê‰‘– )¨‰‚ “‰ã‰Àı( ÷‰Ö‰Î‰‚ı \InE{}$i$\EnE{}ô ş‰ß õ‰Æ‰ƒ‰Â ÷‰ª‰µ‰‚ ª‰Àù ¨‰´. ¢¤ Ÿ‰Ö‰ƒ‰Ö‰´ õ‰Æ‰ƒ‰Â ¥ “‰‚ û‰İ õ‰µ‰Ê‰Û î‰Â¢ö ÷‰Ö‰‘¯ õ‰µ‰ó‰ü “‰‘ ¡‰Î‰¯ õ‰Æ‰µ‰Ö‰ƒ‰İ “‰‚ ¢¨‰´ õ‰üş‰À. Ï‰Âş‰Ö‰‚ı ÷‰Ş‰‘ş‰Ç ¡‰Âø›‰ü ¤øı ¬‰Ô‰½‰‚ı ÷‰Ş‰‘ş‰Ç “‰‚ ş‰ß ¬‰¤– ¨‰´: ğ‰Â ş‰× \InE{}TIN\EnE{} ¤ ¥ “‰‘„ ÷‰Ú‰‘ù ‰ƒ‰İ, “‰‚ ¬‰¤– ş‰× õ‰·‰Ü‰¶“‰€‰Àı ¬‰Ô‰½‰‚ ¢ş‰Àù õ‰üª‰¢. ¢¤ Ÿ‰Ö‰ƒ‰Ö‰´ —‰€‰ú‰‘ ¥øş‰‚ı ¢ş‰Àı  ó‰Ãøõ‰\nasb ‘ û‰Ş‰‚ı ¨‰Î‰¼ ş‰× \InE{}TIN\EnE{} ¤ “‰‚ õ‰‘ ÷‰È‰‘ö õ‰ü¢û‰À, ¥øş‰‚ı 쉑‰İ ¨‰´; ‰ö ¡‰‘¬‰ƒ‰´ õ‰ú‰İ \InE{}TIN\EnE{} ¢¤ ş‰ß ¨‰´  û‰Â ¡‰Í 쉑‰Ş‰ü ¨‰Î‰¼ ö ¤ ¢¤ ¢ì‰ƒ‰Ö‰\nasb ‘ ş‰× ÷‰Ö‰Î‰‚ ì‰Î‰â õ‰ü‰À. “‰€‰‘“‰Âş‰ß ÷‰Ş‰‘ş‰Ç \InE{}TIN\EnE{} ¥ ş‰ß ¥øş‰‚ “‰Æ‰ƒ‰‘¤ ¨‰‘¢ù ¨‰´: ê‰ü ¨‰´ “‰Àøö ¢¤ ÷‰Ñ‰Â ğ‰Âꉵ‰ß ¤—‰Ô‰‘á ÷‰Ö‰‘¯, öû‰‘ ¤ ¢¤ ¬‰Ô‰½‰‚ı ÷‰Ş‰‘ş‰Ç ¤¨‰İ ‰ƒ‰İ. “‰Âı ÷‰Ş‰÷‰‚ı ¡‰Âø›‰ü “‰Â÷‰‘õ‰‚ õ‰ü—‰÷‰ƒ‰À “‰‚ ª‰Ø‰Û \ref{outputexample} ş‰× ÷‰Ş‰÷‰‚ ¥ ¡‰Âø›‰ü ¤øı \InE{}TIN\EnE{} ÷‰È‰‘ö ¢¢ù ª‰Àù ¢¤ ª‰Ø‰Û \ref{inputexample} ¨‰´, —‰›‰‚ ‰ƒ‰À. \begin{figure} \english \hbox{ \hbox to 4cm{\vbox{ \input{outfile} }} \input{outexamp} } \farsi \caption{\label{outputexample} ş‰× ÷‰Ş‰÷‰‚ ¥ ꉑş‰Û ¡‰Âø›‰ü } \end{figure} \english\farsi \section{\label{structure} ¨‰‘¡‰µ‰‘¤ ø —‰“‰â õ‰ú‰İ “‰Â÷‰‘õ‰‚ } ¥“‰‘ö “‰Â÷‰‘õ‰‚÷‰ş‰Æ‰ü õ‰¤¢ ¨‰µ‰Ô‰‘¢ù “‰Âı •‰ƒ‰‘¢ù¨‰‘¥ı ş‰ß ó‰Ú‰¤ş‰µ‰İ, ¥“‰‘ö \InE{}Borland Pascal 7\EnE{} ¨‰´. ¢ó‰ƒ‰Û ÷‰µ‰¿‰‘’ ş‰ß ¥“‰‘ö “‰‚ 䉀‰ö ¥“‰‘ö “‰Â÷‰‘õ‰‚÷‰ş‰Æ‰ü, ¨‰‘¢ù “‰¢ö ø ¡‰÷‰‘ “‰¢ö ş‰ß ¥“‰‘ö ¢¤ õ‰Ö‰‘ş‰Æ‰‚ “‰‘ ¥“‰‘öû‰‘ı ¢ş‰Ú‰Â õ‰‘÷‰€‰À \InE{}C\EnE{} ¨‰´. û‰Ş‰»‰€‰ƒ‰ß —‰Ş‰‘ô 쉑“‰Ü‰ƒ‰´û‰‘ı õ‰¤¢ ÷‰ƒ‰‘¥ ¢¤ ş‰ß ¥“‰‘ö ø›‰¢ ¢¤¢. % ¢¤ ş‰ß›‰‘ ì‰Æ‰Ş‰´û‰‘ş‰ü Ÿ‰Áé ª‰Àù ¨‰´. \section{\label{datastr} ¨‰‘¡‰µ‰Ş‰‘ö ¢¢ùû‰‘ı õ‰¤¢ ¨‰µ‰Ô‰‘¢ù } ¢¤ ş‰ß “‰¿‰Ç ¨‰‘¡‰µ‰Ş‰‘ö ¢¢ùû‰‘ı õ‰ú‰Ş‰ü ¤  ¢¤ •‰ƒ‰‘¢ù¨‰‘¥ı ş‰ß ó‰Ú‰¤ş‰µ‰İ õ‰¤¢ ¨‰µ‰Ô‰‘¢ù ì‰Â¤ ğ‰Âꉵ‰‚÷‰À ¤ “‰Â¤¨‰ü ¡‰û‰ƒ‰İ î‰Â¢. ş‰ß ¨‰‘¡‰µ‰Ş‰‘ö ¢¢ùû‰‘ ¢¤ ş‰÷‰ƒ‰´ \InE{}GEODESIC\EnE{} —‰ã‰Âş‰Ó ª‰Àù÷‰À. % ¢¤ ş‰ß›‰‘ ì‰Æ‰Ş‰´û‰‘ş‰ü Ÿ‰Áé ª‰Àù ¨‰´. \section{\label{difficulty} õ‰È‰Ø‰…– õ‰›‰¢ ¢¤ •‰ƒ‰‘¢ù¨‰‘¥ı } ¢¤ ş‰ß “‰¿‰Ç “‰‚ õ‰È‰Ø‰…– õ‰¿‰µ‰Ü‰Ô‰ü  ¢¤ •‰ƒ‰‘¢ù¨‰‘¥ı ş‰ß ó‰Ú‰¤ş‰µ‰İ “‰‚ öû‰‘ “‰Â¡‰¤¢ î‰Â¢ş‰İ ¡‰û‰ƒ‰İ •‰Â¢¡‰´ ø ¤ø© Ÿ‰Û ş‰ß õ‰È‰Ø‰…– ¤ õ‰Î‰Â ¡‰û‰ƒ‰İ î‰Â¢. % ¢¤ ş‰ß›‰‘ ì‰Æ‰Ş‰´û‰‘ş‰ü Ÿ‰Áé ª‰Àù ¨‰´. \section{\label{test} —‰Æ‰´ “‰Â÷‰‘õ‰‚} ¢¤ ş‰ß “‰¿‰Ç “‰‚ ÷‰½‰ùû‰‘ı —‰Æ‰´ “‰Â÷‰‘õ‰‚ ø ş‰¹‰‘¢ ¢¢ùû‰‘ı —‰Ê‰‘¢ê‰ü ›‰ú‰´ —‰Æ‰´ “‰Â÷‰‘õ‰‚ ¡‰û‰ƒ‰İ •‰Â¢¡‰´. ¢¤ Ÿ‰Ö‰ƒ‰Ö‰´ “‰Âı —‰Æ‰´ “‰Â÷‰‘õ‰‚, “‰‘ş‰À “‰µ‰÷‰ƒ‰İ “‰‚ ¬‰¤– —‰Ê‰‘¢ê‰ü, \InE{}TIN\EnE{} —‰ó‰ƒ‰À ‰ƒ‰İ. û‰Ş‰»‰€‰ƒ‰ß “‰Âı —‰Æ‰´ Ÿ‰‘ó‰´û‰‘ş‰ü  “‰‚ ‰€‰Àø›‰ú‰ü õ‰½‰À’ ÷‰ƒ‰‘¥ ¢¤÷‰À, “‰‘ş‰À “‰µ‰÷‰ƒ‰İ \InE{}TIN\EnE{}û‰‘ı õ‰½‰À’ —‰ó‰ƒ‰À ‰ƒ‰İ. “‰Âı —‰ó‰ƒ‰À ş‰× \InE{}TIN\EnE{} “‰‚ ¬‰¤– \InE{}Random\EnE{}, ê‰ü ¨‰´ —‰ã‰À¢ı ÷‰Ö‰Î‰‚ ¤ “‰‚ ¬‰¤– —‰Ê‰‘¢ê‰ü ¤øı ¬‰Ô‰½‰‚ ÷‰µ‰¿‰‘’ î‰Â¢ù, ş‰ß ÷‰Ö‰Î‰‚û‰‘ ¤ “‰‚ ¤øª‰ü õ‰·‰Ü‰¶“‰€‰Àı ‰ƒ‰İ, ø ¨‰³‰Å “‰‚ û‰Â ş‰× ¥ ş‰ß ÷‰Ö‰‘¯ ş‰× ä‰À¢ —‰Ô‰‘ì‰ü “‰‚ 䉀‰ö ¤—‰Ô‰‘á ö ÷‰Ö‰Î‰‚ ÷‰Æ‰±‰´ ¢û‰ƒ‰İ. •‰Å —‰€‰ú‰‘ õ‰Æ‰ÿ‰Ü‰‚ı õ‰ú‰İ ¢¤ ş‰ß ¥õ‰ƒ‰€‰‚, ¤ø© õ‰·‰Ü‰¶“‰€‰Àı ÷‰Ö‰‘¯ ¨‰´. ¢¤ ş‰ß õ‰¤¢, õ‰‘ ¥ ¤øª‰ü  “‰‚ ¤ø© \InE{}Delaunay\EnE{} õ‰ã‰Âøé ¨‰´ ¨‰µ‰Ô‰‘¢ù î‰Â¢ùş‰İ. \begin{figure} \english \input{vor} \farsi \caption{\label{voronoi} ş‰× ÷‰Ş‰÷‰‚ ¥ ÷‰Ş‰¢¤ \InE{}Voronoi\EnE{}} \end{figure} \english \farsi ¢¤ ş‰ß ¤ø©, “‰‘ş‰À “‰µ‰À ÷‰Ş‰¢¤ \InE{}Voronoi\EnE{} õ‰Â“‰¯ “‰‚ ÷‰Ö‰‘¯ ¤ •‰ƒ‰À ‰ƒ‰İ ø ¨‰³‰Å ¢øğ‰‘ö ö ¤ ¤¨‰İ ‰ƒ‰İ. ¢øğ‰‘ö ÷‰Ş‰¢¤ \InE{}Voronoi\EnE{}, û‰Ş‰‘ö õ‰·‰Ü‰¶“‰€‰Àı \InE{}Delaunay\EnE{} ¨‰´. ÷‰Ş‰¢¤ \InE{}Voronoi\EnE{} õ‰Â“‰¯ “‰‚ \InE{}$n$\EnE{} ÷‰Ö‰Î‰‚, ÷‰Ş‰¢¤ı ¨‰´  ¬‰Ô‰½‰‚ ¤ “‰‚ \InE{}$n$\EnE{} ÷‰‘Ÿ‰ƒ‰‚ —‰Ö‰Æ‰ƒ‰İ“‰€‰Àı õ‰ü‰À “‰‚ ω¤ı  ¢¤ û‰Â ÷‰‘Ÿ‰ƒ‰‚ ¢ì‰ƒ‰Ö‰\nasb ‘ ş‰Ø‰ü ¥ ş‰ß \InE{}$n$\EnE{} ÷‰Ö‰Î‰‚ øì‰â õ‰üª‰¢ ø û‰Â ÷‰Ö‰Î‰‚ ¥ ¬‰Ô‰½‰‚, ¢¤ ÷‰‘Ÿ‰ƒ‰‚ı õ‰Â“‰¯ “‰‚ ÷‰Ö‰Î‰‚ş‰ü )¥ ş‰ß \InE{}$n$\EnE{} ÷‰Ö‰Î‰‚( øì‰â õ‰üª‰¢  “‰‚ ö ÷‰Ã¢ş‰×—‰Â ¨‰´. “‰Âı õ‰·‰‘ñ ¢¤ ª‰Ø‰Û \ref{voronoi} ş‰× ÷‰Ş‰÷‰‚ ¥ ÷‰Ş‰¢¤ \InE{}Voronoi\EnE{} ¤ õ‰ü“‰ƒ‰€‰ƒ‰À. ª‰Ø‰Û \ref{delaunay} õ‰·‰Ü‰¶“‰€‰Àı \InE{}Delaunay\EnE{} ¢øğ‰‘ö ş‰ß ÷‰Ş‰¢¤ ¤ “‰‚ û‰Ş‰Âù ¡‰¢ ÷‰Ş‰¢¤ ÷‰È‰‘ö õ‰ü¢û‰À. \clearpage % “‰Âı Ÿ‰Û õ‰È‰Ø‰Û \InE{}TeX capacity exceeded\EnE{} ®‰‘ꉂ ª‰À. \begin{figure} \english \input{triang} \farsi \caption{\label{delaunay} ş‰× ÷‰Ş‰÷‰‚ ¥ õ‰·‰Ü‰¶“‰€‰Àı \InE{}Delaunay\EnE{}} \end{figure} \english\farsi ¤ø©û‰‘ı ¨‰ƒ‰Ø‰ü “‰Âı “‰‚ ¢¨‰´ ø¤¢ö ÷‰Ş‰¢¤ \InE{}Voronoi\EnE{} ø›‰¢ ¢¤¢  “‰ú‰µ‰Âş‰ß öû‰‘ ¥ ¥õ‰‘ö ›‰Âı \InE{}$O(n\log n)$\EnE{} “‰Â¡‰¤¢¤ ¨‰´. ¢¤ ş‰ß›‰‘ õ‰‘ ¥ ş‰× ó‰Ú‰¤ş‰µ‰İ \InE{}$O(n^2)$\EnE{} “‰Âı ş‰ß ¤ ¨‰µ‰Ô‰‘¢ù î‰Â¢ùş‰İ. ş‰ß ó‰Ú‰¤ş‰µ‰İ “‰Àş‰ß ¬‰¤– 䉪‰Û õ‰ü‰À  “‰Âı û‰Â ş‰× ¥ ÷‰Ö‰‘¯ õ‰‘÷‰€‰À \InE{}$v$\EnE{}, “‰µ‰À ÷‰Ã¢ş‰×—‰Âş‰ß ÷‰Ö‰Î‰‚ “‰‚ ö ¤ •‰ƒ‰À î‰Â¢ù, 䉪‰¢ õ‰€‰Ê‰Ó “‰ƒ‰ß ş‰ß ¢ø ÷‰Ö‰Î‰‚ ¤ ¤¨‰İ õ‰ü‰ƒ‰İ. ş‰ß 䉪‰¢ õ‰€‰Ê‰Ó Ÿ‰µ‰Ş‰\nasb ‘ ›‰Ãø ì‰Æ‰Ş‰µ‰ü ¥ ÷‰Ş‰¢¤ \InE{}Voronoi\EnE{} ¨‰´  \InE{}$v$\EnE{} ¤ ª‰‘õ‰Û õ‰üª‰¢. “‰‘ ş‰ß ì‰Æ‰Ş‰´, ª‰Âøá õ‰ü‰ƒ‰İ ø ş‰ß 䉪‰¢õ‰€‰Ê‰Ó ¤ “‰‘ 䉪‰¢õ‰€‰Ê‰Ó “‰ƒ‰ß ÷‰Ö‰‘¯ ¢ş‰Ú‰Â ø \InE{}$v$\EnE{} ì‰Î‰â õ‰ü¢û‰ƒ‰İ ø øó‰ƒ‰ß ÷‰Ö‰Î‰‚ı —‰Ö‰‘ωâ )“‰‚ ¬‰¤– ¢ø¤ı( ¤ •‰ƒ‰À õ‰ü‰ƒ‰İ ø “‰‚ û‰Ş‰ƒ‰ß ¬‰¤– ¢õ‰‚ õ‰ü¢û‰ƒ‰İ —‰‘ ¢ø“‰‘¤ù “‰‚ û‰Ş‰‘ö ®‰Ü‰â øó‰ü “‰Âğ‰Â¢ş‰İ. ›‰Ã‰ƒ‰‘– õ‰Â“‰¯ “‰‚ ş‰ß ó‰Ú‰¤ş‰µ‰İ ø û‰Ş‰»‰€‰ƒ‰ß ó‰Ú‰¤ş‰µ‰İû‰‘ı “‰ú‰µ‰Â “‰Âı ş‰ß õ‰€‰Ñ‰¤ ¤ õ‰ü—‰÷‰ƒ‰À ¢¤ “‰Æ‰ƒ‰‘¤ı ¥ ‰‘’û‰‘ı û‰€‰À¨‰‚ı õ‰½‰‘¨‰±‰‘—‰ü õ‰‘÷‰€‰À \cite{compgeo} “‰±‰ƒ‰€‰ƒ‰À. û‰Ş‰»‰€‰ƒ‰ß õ‰µ‰ß “‰Â÷‰‘õ‰‚ş‰ü  õ‰·‰Ü‰¶“‰€‰Àı ¤ ÷‰¹‰‘ô õ‰ü¢û‰À ø ¢¤ Ÿ‰Ö‰ƒ‰Ö‰´ “‰‚ ¬‰¤– —‰Ê‰‘¢ê‰ü “‰Âı “‰Â÷‰‘õ‰‚ ¢¢ù —‰ó‰ƒ‰À õ‰ü‰À, ¢¤ •‰ƒ‰¨‰´ \ref{sourceC} õ‰Àù ¨‰´. ¢¤ “‰ã‰Ì‰ü ¥ õ‰¤¢  ÷‰ƒ‰‘¥ “‰‚ —‰ó‰ƒ‰À —‰Æ‰´û‰‘ı õ‰½‰À’ ø›‰¢ ¢ª‰´, “‰‚ ş‰ß ¬‰¤– 䉪‰Û î‰Â¢ş‰İ  õ‰Ö‰À¤ ¤—‰Ô‰‘á ÷‰Ö‰‘¯ ¤ “‰‚ ›‰‘ı ş‰ß  “‰‚ ¬‰¤– —‰Ô‰‘ì‰ü ì‰Â¤ ¢û‰ƒ‰İ, ¥ ş‰× ¤“‰Î‰‚,  ş‰× ¤øş‰‚ı õ‰½‰À’ ¤ õ‰È‰¿‰É õ‰ü‰À “‰‚ ¢¨‰´ õ‰üø¤ş‰İ. “‰Âı õ‰·‰‘ñ ğ‰Â ¤—‰Ô‰‘á û‰Â ÷‰Ö‰Î‰‚ ¤ ¥ ¤“‰Î‰‚ı \InE{}$z=\sqrt{R^2-(x-x_O)^2-(y-y_O)^2}$\EnE{} “‰‚ ¢¨‰´ ø¤ş‰İ, ¢¤ Ÿ‰Ö‰ƒ‰Ö‰´ ¨‰Î‰¼ õ‰‘ ş‰× õ‰·‰Ü‰¶“‰€‰Àı ¥ ¨‰Î‰¼ ş‰× î‰Âù “‰‚ ª‰ã‰‘á \InE{}$R$\EnE{} ø “‰‘ õ‰Âî‰Ã \InE{}$(x_O, y_O)$\EnE{} ¨‰´  õ‰Æ‰Ü‰Ş‰\nasb ‘ ş‰× ¨‰Î‰¼ õ‰½‰À’ ¨‰´. \section{\label{sample} ÷‰Ş‰÷‰‚û‰‘ş‰ü ¥ ¡‰Âø›‰ü “‰Â÷‰‘õ‰‚} ¢¤ ş‰ß “‰¿‰Ç ÷‰Ş‰÷‰‚û‰‘ş‰ü ¥ ¡‰Âø›‰üû‰‘ş‰ü  —‰¨‰Í “‰Â÷‰‘õ‰‚ —‰ó‰ƒ‰À ª‰Àù÷‰À ¤ ¡‰û‰ƒ‰İ ¢ş‰À. ¢¢ùû‰‘ı ø¤ø¢ı ş‰ß ¡‰Âø›‰üû‰‘ —‰¨‰Í “‰Â÷‰‘õ‰‚ş‰ü  ¢¤ “‰¿‰Ç \ref{test} —‰®‰ƒ‰¼ ¢¢ù ª‰À —‰ó‰ƒ‰À ª‰Àù ¨‰´ ø ¡‰Âø›‰ü öû‰‘ “‰‘ ¨‰µ‰Ô‰‘¢ù ¥ ꉑş‰Û ¡‰Âø›‰ü “‰Â÷‰‘õ‰‚ ø “‰‘ ‰× ş‰× “‰Â÷‰‘õ‰‚ı õ‰±‰Àñ “‰‚ ê‰Âõ‰´ \InE{}\TeX\EnE{} —‰±‰Àş‰Û ª‰Àù ¨‰´. % ¢¤ ş‰ß›‰‘ ì‰Æ‰Ş‰´û‰‘ş‰ü Ÿ‰Áé ª‰Àù ¨‰´. \section{\label{runningtime} “‰Â¤¨‰ü ¥õ‰‘ö ›‰Âı “‰Â÷‰‘õ‰‚} ¢¤ ş‰ß “‰¿‰Ç “‰‚ “‰Â¤¨‰ü ¥õ‰‘ö ›‰Âı “‰Â÷‰‘õ‰‚ õ‰ü•‰Â¢¥ş‰İ. û‰Ş‰‘öω¤  ¢¤ “‰¿‰Ç \ref{alg} ğ‰Ô‰µ‰ƒ‰İ, ¥õ‰‘ö ›‰Âı ó‰Ú‰¤ş‰µ‰İ \ref{n2alg} ¥ õ‰Â—‰±‰‚ı \InE{}$O(n^2)$\EnE{} ¨‰´. ¢¤ ş‰ß›‰‘ õ‰ü¡‰û‰ƒ‰İ “‰±‰ƒ‰€‰ƒ‰İ  ş‰‘ ó‰Ú‰¤ş‰µ‰İ •‰ƒ‰‘¢ù¨‰‘¥ı ª‰Àù ¢¤ 䉪‰Û ¥ ş‰ß ¥õ‰‘ö ›‰Â “‰Â¡‰¤¢¤ ¨‰´ ş‰‘ ¡‰ƒ‰Â. “‰Âı ş‰ß õ‰€‰Ñ‰¤, “‰Â÷‰‘õ‰‚ı õ‰Â“‰¯ “‰‚ ó‰Ú‰¤ş‰µ‰İ \ref{n2alg} ¤ “‰Âı —‰ã‰À¢ı ¢¢ùı —‰Ê‰‘¢ê‰ü “‰‘ ÷‰À¥ùû‰‘ı õ‰¿‰µ‰Ü‰Ó ›‰Â õ‰ü‰ƒ‰İ ø ¥õ‰‘ö ›‰Â ¤ ÷‰À¥ù õ‰üğ‰ƒ‰Âş‰İ. \begin{figure} \english \begin{center} \begin{tabular}{|c|c|c|} \hline \kern5mm n \kern5mm & Algorithm 1 & Algorithm 2 \\ \hline 5 & 0.004 sec & 0.003 sec \\ 10 & 0.017 sec & 0.018 sec \\ 15 & 0.034 sec & 0.035 sec \\ 20 & 0.058 sec & 0.065 sec \\ 25 & 0.074 sec & 0.087 sec \\ 30 & 0.108 sec & 0.113 sec \\ 35 & 0.140 sec & 0.147 sec \\ 40 & 0.172 sec & 0.179 sec \\ 45 & 0.197 sec & 0.212 sec \\ 50 & 0.247 sec & 0.260 sec \\ 55 & 0.269 sec & 0.303 sec \\ 60 & 0.312 sec & 0.349 sec \\ 65 & 0.339 sec & 0.384 sec \\ 70 & 0.383 sec & 0.421 sec \\ 75 & 0.433 sec & 0.482 sec \\ 80 & 0.494 sec & 0.511 sec \\ 85 & 0.517 sec & 0.560 sec \\ 90 & 0.575 sec & 0.630 sec \\ 95 & 0.633 sec & 0.670 sec \\ 100 & 0.673 sec & 0.764 sec \\ \hline \end{tabular} \end{center} \farsi \caption{\label{runningtimetable} ›‰Àøñ ¥õ‰‘ö ›‰Âı ó‰Ú‰¤ş‰µ‰İû‰‘} \end{figure} \english\farsi ÷‰Ø‰µ‰‚ı 쉑“‰Û —‰›‰‚ ş‰ß ¨‰´  ¥õ‰‘ö ›‰Âı ó‰Ú‰¤ş‰µ‰İ —‰‘ Ÿ‰À “‰Æ‰ƒ‰‘¤ ¥ş‰‘¢ı ø“‰Æ‰µ‰‚ “‰‚ ÷‰á ¨‰Î‰½‰ü ¨‰´  ó‰Ú‰¤ş‰µ‰İ ¤øı ö ›‰Â õ‰üª‰¢. ¢¤ ¬‰¤—‰ü  ¨‰Î‰¼, —‰‘ Ÿ‰Àø¢ ¥ş‰‘¢ı '¬‰‘é" “‰‘ª‰À, ş‰ã‰€‰ü •‰Æ‰µ‰ü ø “‰Ü‰€‰Àıû‰‘ı ¥ş‰‘¢ı ÷‰Àª‰µ‰‚ “‰‘ª‰À, ¥õ‰‘ö ›‰Â ¡‰ƒ‰Ü‰ü ‰µ‰Â ¡‰û‰À “‰¢. ¢¤ û‰Â ¬‰¤– ¢¤ ş‰ß ›‰‘ “‰Âı ş‰ß  “‰µ‰÷‰ƒ‰İ ¥õ‰‘ö ›‰Âı ó‰Ú‰¤ş‰µ‰İ ¤ “‰Âı ÷‰À¥ùû‰‘ı õ‰¿‰µ‰Ü‰Ó ø¤ø¢ı õ‰µ‰½‰‘ö ‰ƒ‰İ, ¨‰Î‰¼ ¤ “‰‚ ¬‰¤– ş‰× õ‰·‰Ü‰¶“‰€‰Àı î‰Âù ğ‰Âꉵ‰‚ş‰İ ø ‰€‰ƒ‰ß õ‰·‰Ü‰¶“‰€‰Àıû‰‘ş‰ü ¤ “‰‘ —‰ã‰À¢ õ‰¿‰µ‰Ü‰Ô‰ü ¥ ÷‰Ö‰‘¯ ş‰¹‰‘¢ î‰Â¢ùş‰İ ø ¢¤ û‰Â Ÿ‰‘ó‰´ ¥õ‰‘ö ›‰Â ¤ ÷‰À¥ù ğ‰Âꉵ‰‚ş‰İ. ÷‰µ‰ƒ‰¹‰‚ı õ‰½‰‘¨‰±‰‚ı õ‰µ‰¨‰Í ¥õ‰‘ö ›‰Â “‰Âı 001 õ‰¤¢ ¢¢ù ¥ û‰Â ş‰× ¥ ÷‰À¥ùû‰‘ı 5, 01, \ldots, ø 001 ¢¤ ›‰Àøñ ª‰Ø‰Û \ref{runningtimetable} ¡‰…¬‰‚ ª‰Àù ¨‰´. ¢¤ ş‰ß ›‰Àøñ ş‰× ¨‰µ‰ö õ‰Â“‰¯ “‰‚ ¥õ‰‘ö ›‰Âı ó‰Ú‰¤ş‰µ‰İ \ref{alg1} ø ¨‰µ‰ö ¢ş‰Ú‰Â õ‰Â“‰¯ “‰‚ ¥õ‰‘ö ›‰Âı ó‰Ú‰¤ş‰µ‰İ \ref{n2alg} ¨‰´. û‰Ş‰‘ö ω¤  ÷‰µ‰Ñ‰‘¤ ¢¤ş‰İ, õ‰ü“‰ƒ‰€‰ƒ‰À  ¥õ‰‘ö ›‰Âı ó‰Ú‰¤ş‰µ‰İ \ref{n2alg} ¥ ó‰Ú‰¤ş‰µ‰İ \ref{alg1} ‰µ‰Â ¨‰´; øó‰ü “‰‚ ÷‰Ñ‰Â õ‰ü¤¨‰À  õ‰Â—‰±‰‚ı ö ÷‰ƒ‰Ã ‰€‰À›‰Ş‰Ü‰‚ı ¨‰´ )Ÿ‰Àì‰Û ¢¤ Ÿ‰‘ó‰´ õ‰½‰À’(. “‰Âı õ‰È‰‘û‰Àùı “‰ú‰µ‰Â ¤ê‰µ‰‘¤ ó‰Ú‰¤ş‰µ‰İû‰‘ ¥ ÷‰Ñ‰Â ¥õ‰‘ö ›‰Â, “‰‚ ÷‰Ş‰¢¤ ª‰Ø‰Û \ref{graph}  û‰Ş‰‘ö ω…䉑– ›‰Àøñ ê‰ë ¤ ¢¤ “‰Â ¢¤¢, —‰›‰‚ ‰ƒ‰À. “‰‘ —‰›‰‚ “‰‚ ş‰ß ª‰Ø‰Û, õ‰ã‰Ö‰ñ “‰‚ ÷‰Ñ‰Â õ‰ü¤¨‰À  õ‰Â—‰±‰‚ı ¥õ‰‘ö ›‰Âı ó‰Ú‰¤ş‰µ‰İ ¥ \InE{}$O(n^2)$\EnE{} “‰‘ª‰À. \begin{figure} \english \input{graph} \farsi \caption{\label{graph} ÷‰Ş‰¢¤ ¥õ‰‘ö ›‰Âı ó‰Ú‰¤ş‰µ‰İ “‰ÂŸ‰Æ‰° ÷‰À¥ùı ø¤ø¢ı } \end{figure} \english\farsi