موضوع مقاله: هندسه محاسباتی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # هندسه محاسباتی | مقدمه: بعضی از مسائل کاملاً هندسی، برآمده از مطالعهٔ الگوریتمهای هندسهٔ محاسباتی است و مطالعه این‌گونه مسائل نیز به عنوان بخشی از هندسهٔ محاسباتی به حساب می‌آیند. | ## بخش 1: هندسه محاسباتی | انگیزهٔ اصلی برای قلمداد کردن هندسهٔ محاسباتی به عنوان یک رشتهٔ علمی، پیشرفت در گرافیک رایانه‌ای، طراحی و تولیدات با کمک رایانه (به‌وسیلهٔ نرم‌افزارهایی مانند کدCAD/کمCAM) بود؛ ولی طبیعتاً بسیاری از مسائل در هندسهٔ محاسباتی، قدیمی هستند. شاخه‌های اصلی هندسهٔ محاسباتی عبارت‌اند از: هندسهٔ محاسباتی ترکیبی (هندسهٔ الگوریتمی): این هندسهٔ محاسباتی اشیای هندسی را به‌عنوان موجودات گسسته در نظر می‌گیرد. هندسهٔ محاسباتی عددی (هندسهٔ ماشینی، طراحی هندسی با کمک رایانه یا مدل‌سازی هندسی): اساس کار این هندسهٔ محاسباتی به این صورت است که اشیای دنیای واقعی را به‌صورت مناسبی برای محاسبات رایانه‌ای در سیستم‌های کد/کم درمی‌آورد. این شاخه ممکن است به‌عنوان هندسهٔ توصیفی پیشرفته در نظر گرفته شود و اغلب یکی از شاخه‌های گرافیک کامپیوتری یا کَد به حساب می‌آید. برخی از این مسائل به قدری آسان به نظر می‌رسند که تا زمان پیدایش رایانه‌ها مشکل به حساب نمی‌آمدند. می‌توان فاصلهٔ بین جفت نقطه‌ها، که تعدادشان معلوم هست را پیدا کرد و بعد کوچک‌ترین عدد را انتخاب کرد. یک نتیجهٔ کلاسیک در هندسهٔ محاسباتی ایجاد الگوریتمی بود که از مرتبهٔ n log n زمان بگیرد. الگوریتم‌های تصادفی که از مرتبهٔ n زمان می‌برند، علاوه بر الگوریتم‌های تعیین‌کننده‌ای که از مرتبهٔ n log n زمان می‌برند نیز کشف شده‌اند. به همین دلیل است که در هندسهٔ محاسباتی تأکید زیادی روی پیچیدگی محاسباتی شده‌است. انواع سؤالات مسائل اساسی در هندسهٔ محاسباتی را می‌توان با در نظر گرفتن معیارهای گوناگون، به روش‌های گوناگونی طبقه‌بندی کرد. | ## بخش 2: هندسه محاسباتی | مسائل ایستا در این گروه از مسائل، نوعی ورودی داده می‌شود و خروجی متناسب باید به دست بیاید یا پیدا شود. برخی مسائل اساسی این نوع عبارت‌اند از: رویه محدب:Convex hull تعدادی نقطه داریم، کوچک‌ترین چندضلعی یا چندوجهی محدبی را پیدا کنید که دربرگیرندهٔ همه نقطه‌هاست. پیچیدگی محاسباتی برای این دسته از مسائل براساس زمان و فضای (حافظهٔ کامپیوتری) لازم برای حل مسئله تقریب زده می‌شود. اگر فضای جستجو ثابت باشد، پیچیدگی محاسباتی برای این دسته از مسائل بر اساس مطالب زیر تخمین زده می‌شود: زمان و حافظهٔ لازم برای ساختن ساختار داده‌ای که باید در داخل آن جستجو شود. مسائل پویا یکی دیگر از گروه‌های اصلی مسائل، مسائل پویا هستند که در آن‌ها هدف، یافتن الگوریتمی مناسب برای یافتن راه حلی است که بعد از هر تغییر دادهٔ ورودی (اضافه یا حذف کردن عناصر هندسی) تکرار شود. برای مثال، مسئلهٔ جستجوی محدوده را می‌توان با اضافه کردن امکان اضافه یا حذف کردن نقطه‌ها به مسئلهٔ جستجوی پویای محدوده تبدیل کرد. مسئلهٔ پوستهٔ محدب پویا همان کار مسئلهٔ پوستهٔ محدب را برای مجموعهٔ نقاطی که به‌طور پویا تغییر می‌کنند انجام می‌دهد. پیچیدگی محاسباتی این دسته از مسائل با توجه به عوامل زیر تخمین زده می‌شود: زمان و حافظهٔ لازم برای ساختن ساختار داده‌ای که باید در داخل آن جستجو شود. زمان و حافظهٔ لازم برای تغییر دادن ساختار دادهٔ مورد جستجو، بعد از یک تغییر در فضای جستجو. حالت‌های گوناگون می‌توان با برخی داده‌ها به گونه‌ای برخورد کرد که با توجه به محتوایشان جزو هر کدام از گروه‌های معرفی شده قرار گیرند. | ## بخش 3: هندسه محاسباتی | برای مثال، در بسیاری از نمونه‌های گرافیک کامپیوتری یک مسئلهٔ رایج این است که مشخص کند کدام ناحیه از صفحه توسط نشانه‌گر ماوسmouse curser کلیک شده‌است. اما در برخی موارد چند ضلعی مورد نظر تغییرناپذیر است در حالی که نقطه مورد جستجو را به نمایش می‌گذارد. برای مثال، چند ضلعی وارد شده می‌تواند نمایندهٔ مرز یک کشور باشد و نقطه، مکان یک هواپیما و مسئله تعیین کردن این است که آیا هواپیما از مرز عبور کرده‌است یا نه. در نهایت، در مثال‌های بیان شده در گرافیک کامپیوتری ورودی‌های متغیر در ساختارهای دادهٔ پویا ذخیره می‌شوند، تا به حل سوالاتی که مربوط به نقاط داخل چندضلعی است، سرعت بخشد. مسئله‌های اصلی در این نوع از هندسهٔ محاسباتی، مدل‌سازی و ارائهٔ منحنی و سطح است. از نخستین و مهم‌ترین کاربردهای هندسهٔ محاسباتی عددی، کاربرد در کشتی‌سازی، هواپیماسازی و صنایع ماشین‌آلات است. اما امروزه، به دلیل حضور گستردهٔ رایانه‌ها و پیشرفته‌تر شدن آن‌ها حتی جعبه‌های عطر و شامپو نیز با تکنیک‌هایی که برای کشتی‌سازان دههٔ ۱۹۶۰ ناشناخته بود طراحی می‌شوند. مطالعهٔ بیشتر مجلات هندسهٔ محاسباتی الگوریتمی/ترکیبی در پیوند زیر: مجلات در زمینهٔ الگوریتم‌های هندسی فهرستی از مجله‌های معتبر که در زمینهٔ الگوریتم‌های هندسی، پژوهش‌هایی را چاپ کرده‌اند، آمده‌است. توجه شود که با آمدن مجله‌هایی که به هندسهٔ محاسباتی اختصاص یافته‌اند، سهم انتشارات هندسی در مجله‌های علوم کامپیوتر با هدف عمومی و مجله‌های گرافیک کامپیوتری کاهش یافت. | ## جمع‌بندی | هندسهٔ محاسباتی: الگوریتم‌ها و کاربردها (ویراست سوم)، تألیف: مارک دی برگ، اوتفرید چیونگ، مارک وان کریولد، مارک اُورمارس- ترجمه: مهدی ایمان‌پرست، انتشارات دانش نگار، تهران، چاپ اول، ۱۳۹۴.