mathematics
24th September 2010, 11:07 AM
هندسه محاسباتی یکی از شاخه‌های علوم کامپیوتر است که برای حل مسائل هندسی از روش‌های الگوریتمی استفاده می‌کند. بعضی از مسائل کاملاً هندسی، برآمده از مطالعهٔ الگوریتم‌های هندسهٔ محاسباتی است و مطالعه این گونه مسائل نیز به عنوان بخشی از هندسه محاسباتی به حساب می‌آید.
انگیزهٔ اصلی برای قلمداد کردن هندسه محاسباتی به عنوان یک رشتهٔ علمی، پیشرفت در گرافیک کامپیوتری، طراحی و تولیدات با کمک رایانه (به وسیلهٔ نرم‌افزارهایی مانند CAD/CAM) بود. ولی طبیعتاً بسیاری از مسائل در هندسه محاسباتی، قدیمی هستند.
کاربردهای مهم دیگر هندسه محاسباتی در دانش رباتیک (برنامه ریزی حرکتی و مشکلات بصری)، سیستم‌های اطلاعات جغرافیایی(جستجو و مکان‌یابی هندسی، نقشه کشی راه‌ها)، طراحی مدار مجتمع(طراحی و بازبینی هندسی مدارهای مجتمع) و مهندسی با کمک رایانه (برنامه‌ریزی ماشین‌های کنترل عددی)میباشد.
شاخه‌های اصلی هندسه محاسباتی عبارتند از:
* هندسهٔ محاسباتی ترکیبی (هندسه الگوریتمی): این هندسهٔ محاسباتی اشیای هندسی را به عنوان موجودات گسسته در نظر می‌گیرد. براساس کتابی که توسط پرپاراتا و شاموس نوشته شده‌است، لفظ هندسه محاسباتی با این مفهوم، نخستین بار در سال ۱۹۷۵ بیان شده‌است.
* هندسه محاسباتی عددی (هندسه ماشینی، طراحی هندسی با کمک رایانه و یا مدلسازی هندسی): اساس کار این هندسه محاسباتی این است که اشیای دنیای واقعی را به صورت مناسبی برای محاسبات رایانه‌ای در سیستم‌های کد/کم در آورد. این شاخه ممکن است به عنوان هندسه توصیفی پیشرفته در نظر گرفته شود و اغلب یکی از شاخه‌های گرافیک کامپیوتری و یا کد به حساب می‌آید. هندسه محاسباتی با این معنا، از سال ۱۹۷۱ مورد استفاده قرار گرفت.
هندسهٔ محاسباتی ترکيبی
هدف اصلی از پژوهش در زمينهٔ هندسه محاسباتی ترکيبی اين است که، براي حل مسائلی که در زمينه اشيای پايه هندسی(نقاط، خط‌ها، چند ضلعی‌ها، چند وجهی‌ها و ...) مطرح می‌شوند، الگوريتم ها و ساختارهای داده ی مناسبی توليد شود.
برخی از اين مسائل به قدری آسان به نظر می‌رسند که تا زمان پيدايش رایانه‌ها مشکل به حساب نمی‌آمدند. برای مثال به مسئله‌ی نزديک‌ترين جفت توجه کنيد:
* n نقطه در صفحه داريم. دو نقطه‌ای که کمترين فاصله را از يکديگر دارند پيدا کنيد.
می‌توان فاصله بين جفت نقطه‌ها، که تعدادشان معلوم هست را پيدا کرد و بعد کوچک‌ترين عدد را انتخاب کرد. اين الگوريتم از مرتبۀ n2 است. منظور اين است که زمان اجرايش به مربع تعداد نقاط بستگی دارد. يک نتيجهٔ کلاسيک در هندسهٔ محاسباتی ايجاد الگوريتمی بود که از مرتبۀ n log n زمان بگيرد. الگوريتم‌های تصادفی که از مرتبۀ n زمان می‌برند، علاوه بر الگوريتم‌هاي تعيين کننده‌ای که از مرتبۀ n log n زمان می‌برند نيز کشف شده‌اند.
برای GIS جديد، گرافيک کامپيوتری و سيستم‌های طراحی مدارهای مجتمع که روزانه ده‌ها و صدها ميليون نقطه را به کار می‌گيرند، تفاوت بين مرتبۀ n2و مرتبۀ n log n می‌تواند تفاوت بين روزها و ثانيه‌ها محاسبه، باشد. به همين دليل است که در هندسه محاسباتی تاکيد زيادی روی پيچيدگی محاسباتی شده است.
انواع سؤالات
مسائل اساسی در هندسه محاسباتی را می‌توان با در نظر گرفتن معيارهای گوناگون، به روش‌های گوناگونی طبقه‌بندی کرد. يکی از اين رده بندی‌ها در زير آمده است.
مسائل ایستا
در اين گروه ازمسائل، نوعی ورودی داده می‌شود و خروجی متناسب بايد به دست بيايد يا پيدا شود. برخی مسائل اساسی اين نوع عبارتند از:
* پوستهٔ محدب(رويه محدب): تعدادی نقطه داريم، کوچک‌ترين چند ضلعی يا چند وجهی محدبی را پيدا کنيد که دربرگيرندهٔ همه نقطه‌هاست.
* تقاطع پاره خط‌ها: تقاطع‌های بين تعدادی پاره خط را پيدا کنيد.
* دياگرام ورونوی: با دريافت مجموعه‌ای از نقاط، فضا را بر اساس نزديک ترين نقطه تقسيم‌بندی کنيد.
* نزديک‌ترين جفت نقطه: با دريافت مجموعه‌ای از نقاط، دونقطه‌ای را بيابيد که کمترين فاصله را دارند.
* کوتاه‌ترين مسیر اقليدسی: دو نقطه را در فضای اقليدسی (با يک مانع چند وجهی) با کوتاه‌ترين مسير به هم وصل کنيد.
* مثلث بندی چند ضلعی: با دريافت يک چند ضلعی، سطح داخل آن را به تعدادی مثلث تقسيم کنيد.
پيچيدگی محاسباتی برای اين دسته از مسائل براساس زمان و فضای(حافظهٔ کامپيوتری) لازم برای حل مسئله تقريب زده می‌شود .
مسائل جستجوی هندسی
در مسائل جستجوی هندسی ورودی از دو قسمت تشکيل شده است: قسمت فضای جستجو و قسمت جستجو، که در هر مسئله تغيير می‌کند. قسمت فضای جست‌وجو بايد به گونه‌ای پيش پردازش شود که بتواند به نحو مطلوبی به سوالات متعدد جواب دهد.
برخی مسائل اساسي جستجوي هندسي عبارتند از:
* جست‌وجوی محدوده :مجموعه‌ای از نقاط را پيش پردازش می‌کند برای اينکه در داخل محدوده مطلوب، تعداد نقاط را بشمارد.
* محل يابی نقطه: با دريافت فضایی که تقسيم بندی شده، يک ساختار داده توليد می‌کند که به ما می‌گويد نقطه مورد نظر، در کدام قسمت قرار دارد.
* نزديک‌ترين همسايه: مجموعه‌ای از نقاط را به اين منظور پيش پردازش می‌کند که تعیین کند کدام نقطه، به نقطهٔ مورد نظر نزديک‌تر است.
* رديابی پرتو: با دريافت مجموعه‌ای از اجسام در فضا، يک ساختار داده توليد می‌کند تا تعیین کند که پرتوی جستجوی مورد نظر، نخستین بار با کدام جسم برخورد می‌کند.
اگر فضای جستجو ثابت باشد، پيچيدگی محاسباتی برای اين دسته از مسائل بر اساس مطالب زير تخمين زده می‌شود:
* زمان و حافظهٔ لازم برای ساختن ساختار داده‌ای که بايد در داخل آن جستجو شود.
* زمان (و برخی مواقع يک حافظهٔ اضافی) برای پاسخ به جستجوها.
برای حالتی که فضای جستجو تغيير می‌کند، به مسائل پويارجوع کنيد.
مسائل پويا
يکی ديگر از گروه‌های اصلی مسائل، مسائل پويا هستند که در آن‌ها هدف، يافتن الگوريتمی مناسب برای يافتن راه حلی است که بعد از هر تغيير دادهٔ ورودی (اضافه يا حذف کردن عناصر هندسی) تکرار شود. الگوريتم‌های اين نوع مسائل اغلب شامل ساختارهای دادهٔ پويا است. هر کدام از مسائل هندسه محاسباتي را مي توان به مسئلهٔ پويا تبديل کرد. برای مثال، مسئلهٔ جستجوی محدوده را می‌توان با اضافه کردن امکان اضافه يا حذف کردن نقطه‌ها به مسئلهٔ جستجوی پويای محدوده تبديل کرد. مسئلهٔ پوستهٔ محدب پويا همان کار مسئلهٔ پوستهٔ محدب را برای مجموعهٔ نقاطی که به طور پويا تغییر می‌کنند انجام می‌دهد.
پيچيدگی محاسباتی اين دسته از مسائل با توجه به عوامل زير تخمين زده می‌شود:
* زمان و حافظهٔ لازم برای ساختن ساختار داده‌ای که بايد در داخل آن جستجو شود.
* زمان و حافظهٔ لازم برای تغيير دادن ساختار دادهٔ مورد جستجو، بعد از يک تغییر در فضای جستجو.
* زمان (و برخی مواقع يک حافظهٔ اضافی) برای پاسخ به جستجوها.
حالت‌های گوناگون
می‌توان با برخی داده‌ها به گونه‌ای برخورد کرد که با توجه به محتوایشان جزو هر کدام از گروه‌های معرفی شده قرار گیرند. برای مثال، مساله زیر را در نظر بگیرید: نقطه در چند ضلعی: مشخص کنید که یک نقطهٔ مورد نظر داخل چند ضلعی است یا خارج آن. در بسیاری از موارد با این مسئله به عنوان یک تک تیر برخورد می‌شود، یعنی اینکه مربوط به گروه اول است. برای مثال، در بسیاری از نمونه‌های گرافیک کامپیوتری یک مسئلهٔ رایج این است که مشخص کند کدام ناحیه از صفحه توسط نشانه‌گر ماوس کلیک شده است. اما در برخی موارد چند ضلعی مورد نظر تغییر ناپذیر است در حالی که نقطه مورد جستجو را به نمایش می‌گذارد. برای مثال، چند ضلعی وارد شده می‌تواند نمایندهٔ مرز یک کشور باشد و نقطه، مکان یک هواپیما و مسئله تعیین کردن این است که آیا هواپیما از مرز عبور کرده است یا نه. در نهایت، در مثال‌های بیان شده در گرافیک کامپیوتری ورودی‌های متغیر درساختارهای دادهٔ پویا ذخیره می‌شوند، تا به حل سوالاتی که مربوط به نقاط داخل چند ضلعی است، سرعت بخشد.
هندسهٔ محاسباتی عددی
این شاخه به مدل سازی هندسی و طراحی هندسی با کمک کامپیوترنیز معروف است و اغلب تحت کلیدواژه‌یمنحنی‌ها و سطح‌ها دیده می‌شود. مسئله‌های اصلی در این نوع از هندسه‌ی محاسباتی، مدل سازی و ارائهٔ منحنی و سطح میباشد. در اینجا مهم‌ترین ابزارها، منحنی‌های پارامتری و سطح‌های پارامتری هستند، مانند خم‌های بزیر،خم‌ها و سطح‌های نواری. از مهم‌ترین روش‌های غیر پارامتری، روش تنظیم رده است. از نخستین و مهم‌ترین کاربردهای هندسهٔ محاسباتی عددی، کاربرد در کشتی سازی، هواپیماسازی و صنایع ماشین آلات میباشد. اما امروزه، به دلیل حضور گستردهٔ رایانه‌ها و پیشرفته‌تر شدن آن‌ها حتا جعبه‌های عطر و شامپو نیز با تکنیک‌هایی که برای کشتی‌سازان دهه‌ی1960 ناشناخته بود طراحی می‌شوند.
انگیزهٔ اصلی برای قلمداد کردن هندسه محاسباتی به عنوان یک رشتهٔ علمی، پیشرفت در گرافیک کامپیوتری، طراحی و تولیدات با کمک رایانه (به وسیلهٔ نرم‌افزارهایی مانند CAD/CAM) بود. ولی طبیعتاً بسیاری از مسائل در هندسه محاسباتی، قدیمی هستند.
کاربردهای مهم دیگر هندسه محاسباتی در دانش رباتیک (برنامه ریزی حرکتی و مشکلات بصری)، سیستم‌های اطلاعات جغرافیایی(جستجو و مکان‌یابی هندسی، نقشه کشی راه‌ها)، طراحی مدار مجتمع(طراحی و بازبینی هندسی مدارهای مجتمع) و مهندسی با کمک رایانه (برنامه‌ریزی ماشین‌های کنترل عددی)میباشد.
شاخه‌های اصلی هندسه محاسباتی عبارتند از:
* هندسهٔ محاسباتی ترکیبی (هندسه الگوریتمی): این هندسهٔ محاسباتی اشیای هندسی را به عنوان موجودات گسسته در نظر می‌گیرد. براساس کتابی که توسط پرپاراتا و شاموس نوشته شده‌است، لفظ هندسه محاسباتی با این مفهوم، نخستین بار در سال ۱۹۷۵ بیان شده‌است.
* هندسه محاسباتی عددی (هندسه ماشینی، طراحی هندسی با کمک رایانه و یا مدلسازی هندسی): اساس کار این هندسه محاسباتی این است که اشیای دنیای واقعی را به صورت مناسبی برای محاسبات رایانه‌ای در سیستم‌های کد/کم در آورد. این شاخه ممکن است به عنوان هندسه توصیفی پیشرفته در نظر گرفته شود و اغلب یکی از شاخه‌های گرافیک کامپیوتری و یا کد به حساب می‌آید. هندسه محاسباتی با این معنا، از سال ۱۹۷۱ مورد استفاده قرار گرفت.
هندسهٔ محاسباتی ترکيبی
هدف اصلی از پژوهش در زمينهٔ هندسه محاسباتی ترکيبی اين است که، براي حل مسائلی که در زمينه اشيای پايه هندسی(نقاط، خط‌ها، چند ضلعی‌ها، چند وجهی‌ها و ...) مطرح می‌شوند، الگوريتم ها و ساختارهای داده ی مناسبی توليد شود.
برخی از اين مسائل به قدری آسان به نظر می‌رسند که تا زمان پيدايش رایانه‌ها مشکل به حساب نمی‌آمدند. برای مثال به مسئله‌ی نزديک‌ترين جفت توجه کنيد:
* n نقطه در صفحه داريم. دو نقطه‌ای که کمترين فاصله را از يکديگر دارند پيدا کنيد.
می‌توان فاصله بين جفت نقطه‌ها، که تعدادشان معلوم هست را پيدا کرد و بعد کوچک‌ترين عدد را انتخاب کرد. اين الگوريتم از مرتبۀ n2 است. منظور اين است که زمان اجرايش به مربع تعداد نقاط بستگی دارد. يک نتيجهٔ کلاسيک در هندسهٔ محاسباتی ايجاد الگوريتمی بود که از مرتبۀ n log n زمان بگيرد. الگوريتم‌های تصادفی که از مرتبۀ n زمان می‌برند، علاوه بر الگوريتم‌هاي تعيين کننده‌ای که از مرتبۀ n log n زمان می‌برند نيز کشف شده‌اند.
برای GIS جديد، گرافيک کامپيوتری و سيستم‌های طراحی مدارهای مجتمع که روزانه ده‌ها و صدها ميليون نقطه را به کار می‌گيرند، تفاوت بين مرتبۀ n2و مرتبۀ n log n می‌تواند تفاوت بين روزها و ثانيه‌ها محاسبه، باشد. به همين دليل است که در هندسه محاسباتی تاکيد زيادی روی پيچيدگی محاسباتی شده است.
انواع سؤالات
مسائل اساسی در هندسه محاسباتی را می‌توان با در نظر گرفتن معيارهای گوناگون، به روش‌های گوناگونی طبقه‌بندی کرد. يکی از اين رده بندی‌ها در زير آمده است.
مسائل ایستا
در اين گروه ازمسائل، نوعی ورودی داده می‌شود و خروجی متناسب بايد به دست بيايد يا پيدا شود. برخی مسائل اساسی اين نوع عبارتند از:
* پوستهٔ محدب(رويه محدب): تعدادی نقطه داريم، کوچک‌ترين چند ضلعی يا چند وجهی محدبی را پيدا کنيد که دربرگيرندهٔ همه نقطه‌هاست.
* تقاطع پاره خط‌ها: تقاطع‌های بين تعدادی پاره خط را پيدا کنيد.
* دياگرام ورونوی: با دريافت مجموعه‌ای از نقاط، فضا را بر اساس نزديک ترين نقطه تقسيم‌بندی کنيد.
* نزديک‌ترين جفت نقطه: با دريافت مجموعه‌ای از نقاط، دونقطه‌ای را بيابيد که کمترين فاصله را دارند.
* کوتاه‌ترين مسیر اقليدسی: دو نقطه را در فضای اقليدسی (با يک مانع چند وجهی) با کوتاه‌ترين مسير به هم وصل کنيد.
* مثلث بندی چند ضلعی: با دريافت يک چند ضلعی، سطح داخل آن را به تعدادی مثلث تقسيم کنيد.
پيچيدگی محاسباتی برای اين دسته از مسائل براساس زمان و فضای(حافظهٔ کامپيوتری) لازم برای حل مسئله تقريب زده می‌شود .
مسائل جستجوی هندسی
در مسائل جستجوی هندسی ورودی از دو قسمت تشکيل شده است: قسمت فضای جستجو و قسمت جستجو، که در هر مسئله تغيير می‌کند. قسمت فضای جست‌وجو بايد به گونه‌ای پيش پردازش شود که بتواند به نحو مطلوبی به سوالات متعدد جواب دهد.
برخی مسائل اساسي جستجوي هندسي عبارتند از:
* جست‌وجوی محدوده :مجموعه‌ای از نقاط را پيش پردازش می‌کند برای اينکه در داخل محدوده مطلوب، تعداد نقاط را بشمارد.
* محل يابی نقطه: با دريافت فضایی که تقسيم بندی شده، يک ساختار داده توليد می‌کند که به ما می‌گويد نقطه مورد نظر، در کدام قسمت قرار دارد.
* نزديک‌ترين همسايه: مجموعه‌ای از نقاط را به اين منظور پيش پردازش می‌کند که تعیین کند کدام نقطه، به نقطهٔ مورد نظر نزديک‌تر است.
* رديابی پرتو: با دريافت مجموعه‌ای از اجسام در فضا، يک ساختار داده توليد می‌کند تا تعیین کند که پرتوی جستجوی مورد نظر، نخستین بار با کدام جسم برخورد می‌کند.
اگر فضای جستجو ثابت باشد، پيچيدگی محاسباتی برای اين دسته از مسائل بر اساس مطالب زير تخمين زده می‌شود:
* زمان و حافظهٔ لازم برای ساختن ساختار داده‌ای که بايد در داخل آن جستجو شود.
* زمان (و برخی مواقع يک حافظهٔ اضافی) برای پاسخ به جستجوها.
برای حالتی که فضای جستجو تغيير می‌کند، به مسائل پويارجوع کنيد.
مسائل پويا
يکی ديگر از گروه‌های اصلی مسائل، مسائل پويا هستند که در آن‌ها هدف، يافتن الگوريتمی مناسب برای يافتن راه حلی است که بعد از هر تغيير دادهٔ ورودی (اضافه يا حذف کردن عناصر هندسی) تکرار شود. الگوريتم‌های اين نوع مسائل اغلب شامل ساختارهای دادهٔ پويا است. هر کدام از مسائل هندسه محاسباتي را مي توان به مسئلهٔ پويا تبديل کرد. برای مثال، مسئلهٔ جستجوی محدوده را می‌توان با اضافه کردن امکان اضافه يا حذف کردن نقطه‌ها به مسئلهٔ جستجوی پويای محدوده تبديل کرد. مسئلهٔ پوستهٔ محدب پويا همان کار مسئلهٔ پوستهٔ محدب را برای مجموعهٔ نقاطی که به طور پويا تغییر می‌کنند انجام می‌دهد.
پيچيدگی محاسباتی اين دسته از مسائل با توجه به عوامل زير تخمين زده می‌شود:
* زمان و حافظهٔ لازم برای ساختن ساختار داده‌ای که بايد در داخل آن جستجو شود.
* زمان و حافظهٔ لازم برای تغيير دادن ساختار دادهٔ مورد جستجو، بعد از يک تغییر در فضای جستجو.
* زمان (و برخی مواقع يک حافظهٔ اضافی) برای پاسخ به جستجوها.
حالت‌های گوناگون
می‌توان با برخی داده‌ها به گونه‌ای برخورد کرد که با توجه به محتوایشان جزو هر کدام از گروه‌های معرفی شده قرار گیرند. برای مثال، مساله زیر را در نظر بگیرید: نقطه در چند ضلعی: مشخص کنید که یک نقطهٔ مورد نظر داخل چند ضلعی است یا خارج آن. در بسیاری از موارد با این مسئله به عنوان یک تک تیر برخورد می‌شود، یعنی اینکه مربوط به گروه اول است. برای مثال، در بسیاری از نمونه‌های گرافیک کامپیوتری یک مسئلهٔ رایج این است که مشخص کند کدام ناحیه از صفحه توسط نشانه‌گر ماوس کلیک شده است. اما در برخی موارد چند ضلعی مورد نظر تغییر ناپذیر است در حالی که نقطه مورد جستجو را به نمایش می‌گذارد. برای مثال، چند ضلعی وارد شده می‌تواند نمایندهٔ مرز یک کشور باشد و نقطه، مکان یک هواپیما و مسئله تعیین کردن این است که آیا هواپیما از مرز عبور کرده است یا نه. در نهایت، در مثال‌های بیان شده در گرافیک کامپیوتری ورودی‌های متغیر درساختارهای دادهٔ پویا ذخیره می‌شوند، تا به حل سوالاتی که مربوط به نقاط داخل چند ضلعی است، سرعت بخشد.
هندسهٔ محاسباتی عددی
این شاخه به مدل سازی هندسی و طراحی هندسی با کمک کامپیوترنیز معروف است و اغلب تحت کلیدواژه‌یمنحنی‌ها و سطح‌ها دیده می‌شود. مسئله‌های اصلی در این نوع از هندسه‌ی محاسباتی، مدل سازی و ارائهٔ منحنی و سطح میباشد. در اینجا مهم‌ترین ابزارها، منحنی‌های پارامتری و سطح‌های پارامتری هستند، مانند خم‌های بزیر،خم‌ها و سطح‌های نواری. از مهم‌ترین روش‌های غیر پارامتری، روش تنظیم رده است. از نخستین و مهم‌ترین کاربردهای هندسهٔ محاسباتی عددی، کاربرد در کشتی سازی، هواپیماسازی و صنایع ماشین آلات میباشد. اما امروزه، به دلیل حضور گستردهٔ رایانه‌ها و پیشرفته‌تر شدن آن‌ها حتا جعبه‌های عطر و شامپو نیز با تکنیک‌هایی که برای کشتی‌سازان دهه‌ی1960 ناشناخته بود طراحی می‌شوند.