<
<ÒchapterÞ•þ‘¢ù¨‘¥ýÚóðø¤þ—ôÚÒlabelÞÐimplementÐ××
<¢¤ÚþöÚê¬ñÚ—ø®þŸ‘—üÚ¢¤“‘¤ùýÚ•þ‘¢ù¨‘¥ýÚóðø¤þ—õüÚîùÚ¢¤Ú“¡©ÚÒrefÞÐalgÐ×
<—ª¤þžÚª¢Ú¡øûþôÚ¢¢ÆÚõ—öÚî‘õñÚþöÚ“¤÷‘õùÚ¢¤Ú•þø¨–ÚÒrefÞÐsourceAÐ×
<õ¢ùÚ¨–ÆÚþöÚÚ“¤÷‘õùÚ¥Úóðø¤þ—ôÚê¬ñÚÒrefÞÐalgÐ×Ú¢¤ÚŸ‘ó–ÚõŸ¢’
<¨—ê‘¢ùÚõüî÷¢ÆÚó“—ùÚ“ùÚþöÚ¢óþñÚîùÚ¨¯øžÚ÷‘õ÷àôÚõ™ó˜“÷¢ýÚª¢ùÚ¢¤ÚŸ‘ó–
<îóüÚõŸ¢’Ú÷þ¨—÷¢ÚøÚ“÷‘“¤þöÚþöÚóðø¤þ—ôÚ“¤ýÚöû‘Úî‘¤Ú÷õüî÷¢ŠÚì¨õ—ü
<“ùÚóðø¤þ—ôÚ®‘êùÚª¢ùÚ¨–ÚîùÚ“‘Ú¨—ê‘¢ùÚ¥ÚöÚõü—øöÚ“¤ýÚû¤Ú¨¯ž
<÷‘õ÷àôÚõ™ó˜“÷¢ýÚª¢ùþüÚ¾îùÚõü—ø÷¢Úèþ¤õŸ¢’ÚûôÚ“‘ª¢½Úîø—‘ù—¤þöÚõ¨þ¤Ú¤
<•þ¢Úõüî÷¢ËÚû¤Ú÷¢ÚîùÚþöÚì¨õ–Ú®‘êùÚ“¤ýÚŸ‘ó–Úèþ¤õŸ¢’ŠÚ¥Ú¥õ‘öÚ›¤ý
<$O(n^3)$Ú“¤¡ø¤¢¤Ú¨–ÚÚøÚ“÷‘“¤þöÚî÷¢—¤Ú¥Úóðø¤þ—ôÚ¬óüÚ¤ŽùÚª¢ù
<¢¤Ú“¡©ÚÒrefÞÐalgÐ×Ú¨–ŠÚøóüÚ¢¤Úõì‘“ñÚÚ•þ‘¢ù¨‘¥ýÚöÚ“ùÚõ¤—’Ú¨‘¢ù—¤Ú¥
<•þ‘¢ù¨‘¥ýÚóðø¤þ—ôÚ“¡©ÚÒrefÞÐalgÐ×Ú¢¤ÚŸ‘ó–Úèþ¤õŸ¢’Ú¨–ÚøÚäòøùÚ“¤ÚþöÚ
<îø—‘ù—¤þöÚõ¨þ¤Ú“þöÚû¤Ú¢øÚ÷ì¯ùþüÚ¤Ú÷þ¥Ú“ùÚ¢¨–Úõüø¤¢ÆÚ¾øÚ÷ùÚîø—‘ù—¤þöÚõ¨þ¤
<¥ÚþíÚõ“¢»Úõª¡«Ú“ùÚ“ìþùýÚ¤Žø§½Ú“‘Ú—ø›ùÚ“ùÚþöÚ¢òþñŠÚ¨—ê‘¢ùÚ¥Úþö
<óðø¤þ—ôÚ“ùÚ›‘ýÚ—çþþ¤Ú¤ŽùÚª¢ùÚ¢¤Ú“¡©ÚÒrefÞÐnonconvexsecÐ×Ú“¤ýÚŸ‘ó–
<÷‘õŸ¢’ÚõãìøñÚ“ùÚ÷à¤Úõü¤¨¢Æ
<
<¢¤ÚþöÚê¬ñÚ“—¢Ú¢¤Ú“¡©ÚÒrefÞÐioÐ×Úê¤õ–Úø¤ø¢ýÚøÚ¡¤ø›üÚ“¤÷‘õùÚ¤Ú—ª¤þžÚ¡øûþôÚî¤¢Æ
<•§Ú¥ÚöÚ¢¤Ú“¡©ÚÚÒrefÞÐstructureÐ×Ú¨‘¡—‘¤ÚîóüÚ“¤÷‘õùÚøÚõ‘›øñû‘ýÚõ¡—óéÚö
<õø¤¢Ú“¤¤¨üÚì¤¤Ú¡øû¢Úð¤ê–ÚøÚ—ø“âÚõúôÚ“¤÷‘õùÚõã¤êüÚ¡øû÷¢Úª¢Æ
<¨•§Ú¢¤Ú“¡©ÚÒrefÞÐdatastrÐ×Ú¢¤“‘¤ùýÚ¨‘¡—õ‘öÚ¢¢ùû‘ýÚõúõüÚîùÚ¢¤Ú“¤÷‘õùÚ¨—ê‘¢ù
<ª¢ùÚ¨–Ú—ø®þžÚõü¢ûþôÆÚ
<“¡©ÚÒrefÞÐdifficultyÐ×Ú“ùÚ“¤¤¨üÚõªîò–Úõø›ø¢Ú¢¤Ú•þ‘¢ù¨‘¥ý
<þöÚóðø¤þ—ôÚ¡øû¢Ú•¤¢¡–ÆÚ¢¤Ú“¡©ÚÒrefÞÐtestÐ×Ú¤ø©û‘þüÚ“¤ýÚ—¨–Ú“¤÷‘õù
<•þª÷ú‘¢Ú¡øûþôÚî¤¢ÆÚ¢¤Ú÷—ú‘Ú¢¤Ú“¡©û‘ýÚÒrefÞÐsampleÐ×ÚøÚÒrefÞÐrunningtimeÐ×
<÷õø÷ùû‘þüÚ¥Ú¡¤ø›üÚ“¤÷‘õùÚ¤Ú¡øûþôÚ¢þ¢ÚøÚ¥õ‘öÚ›¤ýÚ“¤÷‘õùÚ¤Ú“ùÚ¯ø¤Úõ—ø¨Á
<“¤¤¨üÚ¡øûþôÚî¤¢Æ
<
<ÒsectionÞÒlabelÞÐioÐ×Úø¤ø¢ýÚøÚ¡¤ø›ü×
<ø¤ø¢ýÚ“¤÷‘õùÚ¥Úê‘þóüÚ¨–ÚîùÚ÷‘ôÚöÚ“ùÚä÷øöÚøóþöÚ•‘¤õ—¤Ú¡ÁÚ¢¨—ø¤Ú¾Command Line½
<“ùÚ“¤÷‘õùÚ¢¢ùÚõüªø¢ÆÚþöÚê‘þñÚª‘õñÚõª¡¬‘–ÚþíÚ¨¯žÚ÷‘õ÷àôÚõ™ó˜“÷¢ýÚª¢ùÚ¨–Æ
<“¢þöÚ¬ø¤–ÚîùÚ¢¤Ú¡ÁÚøñÚ—ã¢¢Ú÷ì‘ÁÚ¾$n$½ÚøÚ¨•§Ú—ã¢¢Úõ™ó˜û‘ýÚõø›ø¢Ú¢¤ÚTINÚ¾$m$½
<÷øª—ùÚª¢ùÚ¨–ÆÚ•§Ú¥ÚöÚ¢¤Ú$n$Ú¡ÁÚ“ã¢Ú¢¤Úû¤Ú¡ÁÚ¨ùÚä¢¢ÚŸìþìüÚîùÚ÷ª‘ö¢û÷¢ùýÚ
<õ¡—¬‘–ÚþîüÚ¥Ú÷ì‘ÁÚ¾õ¡—¬‘–Ú¨ùÚ“ã¢ý½Ú¨–Ú÷øª—ùÚª¢ùÚ¨–ÆÚ•§Ú¥ÚþöÚ¡¯øÁŠ
<¢¤Ú$m$Ú¡ÁÚ“ã¢ŠÚ¢¤Úû¤Ú¡ÁÚ¨ùÚä¢¢Ú¬ŸþžÚîùÚ÷ª‘ö¢û÷¢ùýÚªõ‘¤ùýÚ¨ùÚ¤»§ÚþîüÚ¥Úõ™ó˜û‘
<û¨—÷¢Ú÷øª—ùÚª¢ùÚ¨–ÆÚäòøùÚ“¤ÚþöÚ¢¤Ú¡ÁÚ¡¤Úê‘þñÚ¢øÚä¢¢Ú÷øª—ùÚª¢ùÚ¨–
<îùÚªõ‘¤ùýÚ¤Žø§Úõ“¢»ÚøÚõì¬¢Úû¨—÷¢Æ
<“¤ýÚõ™‘ñÚªîñÚÒrefÞÐinputexampleÐ×ÚþíÚ÷õø÷ùÚ¥
<ê‘þñÚø¤ø¢ýÚøÚTINÚõ¤“øÁÚ“ùÚöÚ¤Ú÷ª‘öÚõü¢û¢ÆÚþöÚTINÚª‘õñÚ€Ú¤»§ÚøÚ
<õ™ó˜Ú¨–ÆÚ
<
<ÒbeginÞfigure×
<ÒenglishÚ
>\hbox{
>\hbox to 4cm{\vbox{
>\input{infile}
>}}
>\input{inexamp}
>}
<ÒfarsiÚ
<ÒcaptionÞÒlabelÞÐinputexampleÐ×ÚþíÚ÷õø÷ùÚ¥Úê‘þñÚø¤ø¢ý×
<ÒendÞfigure×
<ÒenglishÒfarsiÚ
<
<¡¤ø›üÚ“¤÷‘õùÚûôÚ¢¤Úê‘þñÚøÚûôÚ“¤Ú¤øýÚ¬êŸùýÚ÷õ‘þ©Ú÷ª‘öÚ¢¢ùÚõüªø¢Æ
<¨ôÚê‘þñÚ¡¤ø›üŠÚ•‘¤õ—¤Ú¢øôÚ¡ÁÚ¢¨—ø¤Ú¨–ÆÚ¢¤Ú¨¯¤ÚøñÚþöÚê‘þñŠÚ—ã¢¢Ú÷ì‘Á
<¤øýÚõ¨þ¤Ú¾“‘ÚŸ—¨‘’Ú÷ì¯ùýÚª¤øáÚøÚ•‘þ‘ö½ÚøÚûõ÷þöÚ¯øñÚõ¨þ¤Ú÷øª—ùÚª¢ùÚ¨–Æ
<¢¤Ú¡Áû‘ýÚ“ã¢ŠÚ¢¤Ú¡ÁÚ$i$ôŠÚõ¡—¬‘–Ú¾¨ùÚ“ã¢ý½Ú÷ì¯ùýÚ$i$ôÚþöÚõ¨þ¤Ú÷øª—ù
<ª¢ùÚ¨–ÆÚ¢¤ÚŸìþì–Úõ¨þ¤Ú¥Ú“ùÚûôÚõ—¬ñÚî¤¢öÚ÷ì‘ÁÚõ—øóüÚ“‘Ú¡¯øÁÚõ¨—ìþô
<“ùÚ¢¨–Úõüþ¢Æ
<
<¯¤þìùýÚ÷õ‘þ©Ú¡¤ø›üÚ¤øýÚ¬êŸùýÚ÷õ‘þ©Ú“ùÚþöÚ¬ø¤–Ú¨–Ê
<ð¤ÚþíÚTINÚ¤Ú¥Ú“‘òÚ÷ð‘ùÚî÷þôŠÚ“ùÚ¬ø¤–ÚþíÚõ™ó˜“÷¢ýÚ¬êŸùÚ¢þ¢ùÚõüªø¢Æ
<¢¤ÚŸìþì–Ú—÷ú‘Ú¥øþùýÚ¢þ¢ýÚîùÚó¥øõ‘³ÚûõùýÚ¨¯žÚþíÚTINÚ¤Ú“ùÚõ‘Ú÷ª‘öÚõü¢û¢Š
<¥øþùýÚì‘ŽôÚ¨–ËÚøöÚ¡‘¬þ–ÚõúôÚTINÚ¢¤ÚþöÚ¨–ÚîùÚû¤Ú¡ÁÚì‘ŽõüÚ¨¯žÚöÚ¤Ú
<¢¤Ú¢ìþì‘³ÚþíÚ÷ì¯ùÚì¯âÚõüî÷¢ÆÚ“÷‘“¤þöÚ÷õ‘þ©ÚTINÚ¥ÚþöÚ¥øþùÚ“¨þ‘¤
<¨‘¢ùÚ¨–ÊÚÚî‘êüÚ¨–Ú“¢øöÚ¢¤Ú÷à¤Úð¤ê—öÚ¤—ê‘áÚ÷ì‘ÁŠÚöû‘Ú¤Ú¢¤Ú¬êŸùý
<÷õ‘þ©Ú¤¨ôÚî÷þôÆÚ“¤ýÚ÷õø÷ùýÚ¡¤ø›üÚ“¤÷‘õùÚõü—ø÷þ¢Ú“ùÚªîñÚÒrefÞÐoutputexampleÐ×
<þíÚ÷õø÷ùÚ¥Ú¡¤ø›üÚ¤øýÚTINÚ÷ª‘öÚ¢¢ùÚª¢ùÚ¢¤ÚªîñÚÒ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Ð×Ú¨‘¡—‘¤ÚøÚ—ø“âÚõúôÚ“¤÷‘õùÚ×
<¥“‘öÚ“¤÷‘õù÷øþ¨üÚõø¤¢Ú¨—ê‘¢ùÚ“¤ýÚ•þ‘¢ù¨‘¥ýÚþöÚóðø¤þ—ôŠÚ¥“‘öÚ
<Borland Pascal 7Ú¨–ÆÚ¢óþñÚ÷—¡‘’ÚþöÚ¥“‘öÚ“ùÚä÷øöÚ¥“‘öÚ“¤÷‘õù÷øþ¨üŠ
<¨‘¢ùÚ“ø¢öÚøÚ¡ø÷‘Ú“ø¢öÚþöÚ¥“‘öÚ¢¤Úõì‘þ¨ùÚ“‘Ú¥“‘öû‘ýÚ¢þð¤Úõ‘÷÷¢ÚCÚ¨–Æ
<ûõ÷þöÚ—õ‘ôÚì‘“óþ–û‘ýÚõø¤¢Ú÷þ‘¥Ú¢¤ÚþöÚ¥“‘öÚø›ø¢Ú¢¤¢Æ
<
<·Ú¢¤Úþö›‘Úì¨õ–û‘þüÚŸ£éÚª¢ùÚ¨–Æ
<
<ÒsectionÞÒlabelÞÐdatastrÐ×Ú¨‘¡—õ‘öÚ¢¢ùû‘ýÚõø¤¢Ú¨—ê‘¢ùÚ×
<¢¤ÚþöÚ“¡©Ú¨‘¡—õ‘öÚ¢¢ùû‘ýÚõúõüÚ¤ÚîùÚ¢¤Ú•þ‘¢ù¨‘¥ýÚþöÚóðø¤þ—ôÚõø¤¢
<¨—ê‘¢ùÚì¤¤Úð¤ê—ù÷¢Ú¤Ú“¤¤¨üÚ¡øûþôÚî¤¢ÆÚþöÚ¨‘¡—õ‘öÚ¢¢ùû‘Ú¢¤Úþø÷þ–
<GEODESICÚ—ã¤þéÚª¢ù÷¢Æ
<
<·Ú¢¤Úþö›‘Úì¨õ–û‘þüÚŸ£éÚª¢ùÚ¨–Æ
<
<ÒsectionÞÒlabelÞÐdifficultyÐ×Úõªîò–Úõø›ø¢Ú¢¤Ú•þ‘¢ù¨‘¥ýÚ×
<¢¤ÚþöÚ“¡©ÚÚ“ùÚõªîò–Úõ¡—óêüÚîùÚ¢¤Ú•þ‘¢ù¨‘¥ýÚþöÚóðø¤þ—ôÚ“ùÚöû‘Ú“¤¡ø¤¢
<î¤¢þôÚ¡øûþôÚ•¤¢¡–ÚøÚ¤ø©ÚŸñÚþöÚõªîò–Ú¤Úõ¯¤žÚ¡øûþôÚî¤¢ÆÚ
<
<·Ú¢¤Úþö›‘Úì¨õ–û‘þüÚŸ£éÚª¢ùÚ¨–Æ
<
<ÒsectionÞÒlabelÞÐtestÐ×Ú—¨–Ú“¤÷‘õù×
<¢¤ÚþöÚ“¡©Ú“ùÚ÷Ÿøùû‘ýÚ—¨–Ú“¤÷‘õùÚøÚþ›‘¢Ú¢¢ùû‘ýÚ—¬‘¢êüÚ›ú–Ú—¨–Ú“¤÷‘õù
<¡øûþôÚ•¤¢¡–ÆÚ¢¤ÚŸìþì–Ú“¤ýÚ—¨–Ú“¤÷‘õùŠÚ“‘þ¢Ú“—ø÷þôÚ“ùÚ¬ø¤–Ú—¬‘¢êüŠ
<TINÚ—øóþ¢Úî÷þôÆÚûõ÷þöÚÚ“¤ýÚ—¨–ÚŸ‘ó–û‘þüÚîùÚ“ùÚ÷¢ø›úüÚõŸ¢’Ú÷þ‘¥Ú¢¤÷¢Š
<“‘þ¢Ú“—ø÷þôÚTINû‘ýÚõŸ¢’Ú—øóþ¢Úî÷þôÆ
<
<“¤ýÚ—øóþ¢ÚþíÚTINÚ“ùÚ¬ø¤–ÚRandomŠÚî‘êüÚ¨–Ú—ã¢¢ýÚ÷ì¯ùÚ¤Ú“ùÚ¬ø¤–
<—¬‘¢êüÚ¤øýÚ¬êŸùÚ÷—¡‘’Úî¤¢ùŠÚþöÚ÷ì¯ùû‘Ú¤Ú“ùÚ¤øªüÚõ™ó˜“÷¢ýÚî÷þôŠÚøÚ
<¨•§Ú“ùÚû¤ÚþíÚ¥ÚþöÚ÷ì‘ÁÚþíÚä¢¢Ú—ê‘ìüÚ“ùÚä÷øöÚ¤—ê‘áÚöÚ÷ì¯ùÚ÷¨“–
<¢ûþôÆÚ•§Ú—÷ú‘Úõ¨ŽóùýÚõúôÚ¢¤ÚþöÚ¥õþ÷ùŠÚ¤ø©ÚÚõ™ó˜“÷¢ýÚ÷ì‘ÁÚ¨–Æ
<¢¤ÚþöÚõø¤¢ŠÚõ‘Ú¥Ú¤øªüÚîùÚ“ùÚ¤ø©ÚDelaunayÚõã¤øéÚ¨–Ú¨—ê‘¢ùÚî¤¢ùþôÆ
<
<ÒbeginÞfigure×
<ÒenglishÚ
<ÒinputÞÐvorÐ×
<ÒfarsiÚ
<ÒcaptionÞÒlabelÞÐvoronoiÐ×ÚþíÚ÷õø÷ùÚ¥Ú÷õø¢¤ÚVoronoi×
<ÒendÞfigure×
<ÒenglishÚÒfarsiÚ
<
<¢¤ÚþöÚ¤ø©ŠÚ“‘þ¢Ú“—¢Ú÷õø¢¤ÚÚVoronoiÚõ¤“øÁÚ“ùÚ÷ì‘ÁÚ¤Ú•þ¢Úî÷þôÚøÚ
<¨•§Ú¢øð‘öÚöÚ¤Ú¤¨ôÚî÷þôÆÚ¢øð‘öÚ÷õø¢¤ÚVoronoiŠÚûõ‘öÚõ™ó˜“÷¢ýÚDelaunay
<¨–ÆÚ÷õø¢¤ÚVoronoiÚõ¤“øÁÚ“ùÚ$n$Ú÷ì¯ùŠÚ÷õø¢¤ýÚ¨–ÚîùÚ¬êŸùÚ¤Ú“ùÚ$n$
<÷‘ŸþùÚ—ì¨þô“÷¢ýÚõüî÷¢Ú“ùÚ¯ø¤ýÚîùÚ¢¤Úû¤Ú÷‘ŸþùÚ¢ìþì‘³ÚþîüÚ¥ÚþöÚ$n$
<÷ì¯ùÚøìâÚõüªø¢ÚøÚû¤Ú÷ì¯ùÚ¥Ú¬êŸùŠÚ¢¤Ú÷‘ŸþùýÚõ¤“øÁÚ“ùÚ÷ì¯ùþüÚ¾¥ÚþöÚ$n$Ú÷ì¯ù½Ú
<øìâÚõüªø¢ÚîùÚ“ùÚöÚ÷¥¢þí—¤Ú¨–ÆÚ“¤ýÚõ™‘ñÚ¢¤ÚªîñÚÒrefÞÐvoronoiÐ×
<þíÚ÷õø÷ùÚ¥Ú÷õø¢¤ÚVoronoiÚ¤ÚÚõü“þ÷þ¢ÆÚªîñÚÒrefÞÐdelaunayÐ×Úõ™ó˜“÷¢ý
<DelaunayÚ¢øð‘öÚþöÚ÷õø¢¤Ú¤Ú“ùÚûõ¤ùÚ¡ø¢Ú÷õø¢¤Ú÷ª‘öÚõü¢û¢Æ
<
<ÒclearpageÚÚÚÚÚÚÚÚÚÚ·Ú“¤ýÚŸñÚõªîñÚTeX capacity exceededÚ®‘êùÚª¢Æ
<ÒbeginÞfigure×
<ÒenglishÚ
<ÒinputÞÐtriangÐ×
<ÒfarsiÚ
<ÒcaptionÞÒlabelÞÐdelaunayÐ×ÚþíÚ÷õø÷ùÚ¥Úõ™ó˜“÷¢ýÚDelaunay×
<ÒendÞfigure×
<ÒenglishÒfarsiÚ
<
<¤ø©û‘ýÚîò¨þîüÚ“¤ýÚ“ùÚ¢¨–Úø¤¢öÚ÷õø¢¤ÚVoronoiÚø›ø¢Ú¢¤¢ÚîùÚ“ú—¤þöÚöû‘ÚÚ
<¥Ú¥õ‘öÚ›¤ýÚ$O(n\log n)$Ú“¤¡ø¤¢¤Ú¨–ÆÚ¢¤Úþö›‘Úõ‘Ú¥
<þíÚóðø¤þ—ôÚ$O(n^2)$Ú“¤ýÚþöÚî‘¤Ú¨—ê‘¢ùÚî¤¢ùþôÆÚþöÚóðø¤þ—ôÚ“¢þö
<¬ø¤–ÚäõñÚõüî÷¢ÚîùÚ“¤ýÚû¤ÚþíÚ¥Ú÷ì‘ÁÚõ‘÷÷¢Ú$v$ŠÚ“—¢Ú÷¥¢þí—¤þöÚ÷ì¯ùÚ“ùÚöÚ¤
<•þ¢Úî¤¢ùŠÚäõø¢Úõ÷¬éÚ“þöÚþöÚ¢øÚ÷ì¯ùÚ¤Ú¤¨ôÚõüî÷þôÆÚþöÚäõø¢Úõ÷¬éÚŸ—õ‘³
<›¥øÚì¨õ—üÚ¥Ú÷õø¢¤ÚVoronoiÚ¨–ÚîùÚ$v$Ú¤Úª‘õñÚõüªø¢ÆÚ“‘ÚþöÚì¨õ–ŠÚª¤øá
<õüî÷þôÚøÚþöÚäõø¢õ÷¬éÚ¤Ú“‘Úäõø¢õ÷¬éÚ“þöÚ÷ì‘ÁÚ¢þð¤ÚøÚ$v$Úì¯âÚõü¢ûþôÚøÚøóþö
<÷ì¯ùýÚ—ì‘¯âÚ¾“ùÚ¬ø¤–Ú¢ø¤ý½Ú¤Ú•þ¢Úõüî÷þôÚøÚ“ùÚûõþöÚ¬ø¤–Ú¢õùÚõü¢ûþôÚ—‘
<¢ø“‘¤ùÚÚ“ùÚûõ‘öÚ®óâÚøóüÚ“¤ð¤¢þôÆÚ›¥Žþ‘–Úõ¤“øÁÚ“ùÚþöÚóðø¤þ—ôÚøÚûõ÷þö
<óðø¤þ—ôû‘ýÚ“ú—¤Ú“¤ýÚþöÚõ÷àø¤Ú¤Úõü—ø÷þ¢Ú¢¤Ú“¨þ‘¤ýÚ¥Úî—‘’û‘ýÚû÷¢¨ùý
<õŸ‘¨“‘—üÚõ‘÷÷¢ÚÒciteÞÐcompgeoÐ×Ú““þ÷þ¢ÆÚûõ÷þöÚõ—öÚ“¤÷‘õùþüÚîùÚõ™ó˜“÷¢ý
<¤Ú÷›‘ôÚõü¢û¢ÚøÚ¢¤ÚŸìþì–Ú“ùÚ¬ø¤–Ú—¬‘¢êüÚ“¤ýÚ“¤÷‘õùÚ¢¢ùÚ—øóþ¢Úõüî÷¢Š
<¢¤Ú•þø¨–ÚÒrefÞÐsourceCÐ×Úõ¢ùÚ¨–Æ
<
<¢¤Ú“ã®üÚ¥Úõø¤¢ÚîùÚ÷þ‘¥Ú“ùÚ—øóþ¢Ú—¨–û‘ýÚõŸ¢’Úø›ø¢Ú¢ª–ŠÚ“ùÚþö
<¬ø¤–ÚäõñÚî¤¢þôÚîùÚõì¢¤Ú¤—ê‘áÚ÷ì‘ÁÚ¤Ú“ùÚ›‘ýÚþöÚîùÚ“ùÚ¬ø¤–Ú—ê‘ìü
<ì¤¤Ú¢ûþôŠÚ¥ÚþíÚ¤“¯ùŠÚîùÚþíÚ¤øþùýÚõŸ¢’Ú¤Úõª¡«Úõüî÷¢Ú“ùÚ¢¨–Úõüø¤þôÆ
<“¤ýÚõ™‘ñÚð¤Ú¤—ê‘áÚû¤Ú÷ì¯ùÚ¤Ú¥Ú¤“¯ùýÚ$z=\sqrt{R^2-(x-x_O)^2-(y-y_O)^2}$
<“ùÚ¢¨–Úø¤þôŠÚ¢¤ÚŸìþì–ÚÚ¨¯žÚõ‘ÚþíÚõ™ó˜“÷¢ýÚ¥Ú¨¯žÚþíÚî¤ùÚ“ùÚªã‘á
<$R$ÚøÚ“‘Úõ¤î¥Ú$(x_O, y_O)$Ú¨–ÚîùÚõ¨óõ‘³ÚþíÚ¨¯žÚõŸ¢’Ú¨–ÆÚ
<
<ÒsectionÞÒlabelÞÐsampleÐ×Ú÷õø÷ùû‘þüÚ¥Ú¡¤ø›üÚ“¤÷‘õù×
<¢¤ÚþöÚ“¡©Ú÷õø÷ùû‘þüÚ¥Ú¡¤ø›üû‘þüÚîùÚ—ø¨ÁÚ“¤÷‘õùÚ—øóþ¢Úª¢ù÷¢Ú¤Ú¡øûþôÚ¢þ¢Æ
<¢¢ùû‘ýÚø¤ø¢ýÚþöÚ¡¤ø›üû‘Ú—ø¨ÁÚ“¤÷‘õùþüÚîùÚ¢¤Ú“¡©ÚÒrefÞÐtestÐ×Ú—ø®þžÚ¢¢ù
<ª¢Ú—øóþ¢Úª¢ùÚ¨–ÚøÚ¡¤ø›üÚöû‘Ú“‘Ú¨—ê‘¢ùÚ¥Úê‘þñÚ¡¤ø›üÚ“¤÷‘õùÚøÚ“‘ÚîõíÚþí
<“¤÷‘õùýÚõ“¢ñÚ“ùÚê¤õ–Ú\TeXÚ—“¢þñÚª¢ùÚ¨–Æ
<
<·Ú¢¤Úþö›‘Úì¨õ–û‘þüÚŸ£éÚª¢ùÚ¨–Æ
<
<ÒsectionÞÒlabelÞÐrunningtimeÐ×Ú“¤¤¨üÚ¥õ‘öÚ›¤ýÚ“¤÷‘õù×
<¢¤ÚþöÚ“¡©Ú“ùÚ“¤¤¨üÚ¥õ‘öÚ›¤ýÚ“¤÷‘õùÚõü•¤¢¥þôÆÚûõ‘ö¯ø¤ÚîùÚ¢¤Ú“¡©ÚÒrefÞÐalgÐ×
<ðê—þôŠÚ¥õ‘öÚ›¤ýÚóðø¤þ—ôÚÒrefÞÐn2algÐ×Ú¥Úõ¤—“ùýÚ$O(n^2)$Ú¨–ÆÚ¢¤Úþö›‘Ú
<õü¡øûþôÚ““þ÷þôÚîùÚþ‘Úóðø¤þ—ôÚ•þ‘¢ù¨‘¥ýÚª¢ùÚ¢¤ÚäõñÚ¥ÚþöÚ¥õ‘öÚ›¤
<“¤¡ø¤¢¤Ú¨–Úþ‘Ú¡þ¤ÆÚ“¤ýÚþöÚõ÷àø¤ŠÚ“¤÷‘õùýÚõ¤“øÁÚ“ùÚóðø¤þ—ôÚÒ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Ú
<
<÷î—ùýÚì‘“ñÚ—ø›ùÚþöÚ¨–ÚîùÚ¥õ‘öÚ›¤ýÚóðø¤þ—ôÚ—‘ÚŸ¢Ú“¨þ‘¤
<¥þ‘¢ýÚø“¨—ùÚ“ùÚ÷øáÚ¨¯ŸüÚ¨–ÚîùÚóðø¤þ—ôÚ¤øýÚöÚ›¤Úõüªø¢ÆÚ¢¤Ú¬ø¤—üÚîù
<¨¯žŠÚ—‘ÚŸ¢ø¢Ú¥þ‘¢ýÚÃ¬‘éÀÚ“‘ª¢ŠÚþã÷üÚ•¨—üÚøÚ“ó÷¢ýû‘ýÚ¥þ‘¢ýÚ÷¢ª—ùÚ“‘ª¢ŠÚ¥õ‘ö
<›¤Ú¡þóüÚîõ—¤Ú¡øû¢Ú“ø¢ÆÚ¢¤ÚÚû¤Ú¬ø¤–Ú¢¤ÚþöÚ›‘Ú“¤ýÚþöÚîùÚ“—ø÷þôÚ¥õ‘ö
<›¤ýÚóðø¤þ—ôÚ¤Ú“¤ýÚ÷¢¥ùû‘ýÚõ¡—óéÚø¤ø¢ýÚõ—Ÿ‘öÚî÷þôŠÚ¨¯žÚ¤Ú“ùÚ¬ø¤–
<þíÚõ™ó˜“÷¢ýÚî¤ùÚð¤ê—ùþôÚøÚ÷þöÚõ™ó˜“÷¢ýû‘þüÚ¤Ú“‘Ú—ã¢¢Úõ¡—óêüÚ¥Ú÷ì‘ÁÚ
<þ›‘¢Úî¤¢ùþôÚøÚ¢¤Úû¤ÚŸ‘ó–Ú¥õ‘öÚ›¤Ú¤Ú÷¢¥ùÚð¤ê—ùþôÆÚ÷—þ›ùýÚõŸ‘¨“ùý
<õ—ø¨ÁÚÚ¥õ‘öÚ›¤Ú“¤ýÚ€€Úõø¤¢Ú¢¢ùÚ¥Úû¤ÚþíÚ¥Ú÷¢¥ùû‘ýÚ…ŠÚ€ŠÚÒldotsŠ
<øÚ€€Ú¢¤Ú›¢øñÚªîñÚÒrefÞÐrunningtimetableÐ×Ú¡ò¬ùÚª¢ùÚ¨–ÆÚ¢¤ÚþöÚ›¢øñÚþíÚ¨—øöÚõ¤“øÁÚ“ùÚ¥õ‘öÚ›¤ý
<óðø¤þ—ôÚÒrefÞÐalg1Ð×ÚøÚ¨—øöÚ¢þð¤Úõ¤“øÁÚ“ùÚ¥õ‘öÚ›¤ýÚóðø¤þ—ôÚÒrefÞÐn2algÐ×
<¨–ÆÚ
<
<ûõ‘öÚ¯ø¤ÚîùÚ÷—à‘¤Ú¢¤þôŠÚõü“þ÷þ¢ÚîùÚ¥õ‘öÚ›¤ýÚóðø¤þ—ôÚÒrefÞÐn2algÐ×
<¥ÚÚóðø¤þ—ôÚÒrefÞÐalg1Ð×Úîõ—¤Ú¨–ËÚøóüÚ“ùÚ÷à¤Úõü¤¨¢ÚîùÚõ¤—“ùýÚöÚ÷þ¥
<÷¢›õóùýÚ¨–Ú¾Ÿ¢ìñÚ¢¤ÚŸ‘ó–ÚõŸ¢’½ÆÚ“¤ýÚõª‘û¢ùýÚ“ú—¤Ú¤ê—‘¤Úóðø¤þ—ôû‘Ú¥
<÷à¤Ú¥õ‘öÚ›¤ŠÚ“ùÚ÷õø¢¤ÚªîñÚÒrefÞÐgraphÐ×ÚîùÚûõ‘öÚ¯òä‘–Ú›¢øñÚêøëÚ¤Ú
<¢¤Ú“¤Ú¢¤¢ŠÚ—ø›ùÚî÷þ¢Æ
<“‘Ú—ø›ùÚ“ùÚþöÚªîñŠÚõãìøñÚ“ùÚ÷à¤Úõü¤¨¢ÚîùÚõ¤—“ùýÚ¥õ‘öÚ›¤ýÚóðø¤þ—ôÚ¥
<$O(n^2)$Ú“‘ª¢Æ
<
<ÒbeginÞfigure×
<ÒenglishÚ
<ÒinputÞÐgraphÐ×
<ÒfarsiÚ
<ÒcaptionÞÒlabelÞÐgraphÐ×Ú÷õø¢¤Ú¥õ‘öÚÚ›¤ýÚóðø¤þ—ôÚ“¤Ÿ¨’Ú÷¢¥ùýÚø¤ø¢ýÚ×
<ÒendÞfigure×
<ÒenglishÒfarsiÚ
<