هندسه محاسباتی شاخه ای از علوم رایانه است که به مطالعه الگوریتم ها اختصاص دارد که می تواند از نظر هندسه بیان شود . برخی از مشکلات صرفاً هندسی از مطالعه الگوریتم های هندسی محاسباتی بوجود می آیند و چنین مشکلاتی نیز جزئی از هندسه محاسباتی محسوب می شوند. در حالی که هندسه محاسباتی مدرن یک تحول اخیر است ، یکی از قدیمی ترین زمینه های محاسبات با تاریخچه به دوران باستان است.

 

پیچیدگی محاسباتی برای هندسه محاسباتی از اهمیت ویژه ای برخوردار است ، اگر از الگوریتم های داده های بسیار بزرگ حاوی ده ها یا صدها میلیون نقطه استفاده شود ، الگوریتم ها از اهمیت عملی زیادی برخوردار هستند. برای چنین مجموعه هایی ، تفاوت بین ?(O ( n 2  و( O ( n log n  ممکن است تفاوت بین روز و ثانیه محاسبه باشد.

انگیزه اصلی برای توسعه هندسه محاسباتی به عنوان یک رشته پیشرفت در گرافیک رایانه و طراحی و ساخت به کمک رایانه ( CAD / CAM ) بود ، اما بسیاری از مشکلات در هندسه محاسباتی از نظر کلاسیک است و ممکن است از تجسم ریاضی ناشی شود .

سایر کاربردهای مهم هندسه محاسباتی شامل رباتیک ( برنامه ریزی حرکت و مشکلات دید) ، سیستم های اطلاعات جغرافیایی (GIS) (مکان هندسی و جستجو ، برنامه ریزی مسیر) ، طراحی مدار مجتمع (طراحی و تأیید هندسه IC) ، مهندسی رایانه (CAE) (تولید مش) ، دید رایانه ( بازسازی سه بعدی ).

شاخه های اصلی هندسه محاسباتی عبارتند از:

  • هندسه محاسباتی ترکیبی ، همچنین هندسه الگوریتمی نامیده می شود ، که با اشیاء هندسی به عنوان اشخاص گسسته سروکار دارد . اولین کتاب استفاده از اصطلاحات آماده سازی وشاموس اولین استفاده از اصطلاح "هندسه محاسباتی" به این معنا تا سال 1975 است. [1]
  • هندسه محاسباتی عددی ، که به آن هندسه ماشین ، طراحی هندسی به کمک کامپیوتر (CAGD) یا مدل سازی هندسی نیز گفته می شود ، که در درجه اول با نمایندگی اشیاء دنیای واقعی به اشکال مناسب برای محاسبات رایانه ای در سیستم های CAD / CAM سرو کار دارد. این شاخه ممکن است به عنوان توسعه بیشتر هندسه توصیفی تلقی شود و اغلب شاخه ای از گرافیک رایانه ای یا CAD در نظر گرفته می شود. اصطلاح "هندسه محاسباتی" در این معنی از سال 1971 مورد استفاده قرار گرفته است. [2]

 

فهرست

هندسه محاسباتی ترکیبی [ ویرایش ]

هدف اصلی تحقیق در هندسه محاسباتی ترکیبی ، توسعه الگوریتم های کارآمد و ساختار داده برای حل مشکلات بیان شده از نظر اشیاء اصلی هندسی است: نقاط ، بخش های خط ، چند ضلعی ها ، چند ضلعی و غیره.

برخی از این مشکلات به قدری ساده به نظر می رسند که تا زمان ظهور رایانه ها به هیچ عنوان به عنوان مشکل در نظر گرفته نمی شدند . به عنوان مثال ، نزدیکترین مشکل جفت را در نظر بگیرید :

  • با توجه به تعداد نقاط در هواپیما ، این دو را با کمترین فاصله از یکدیگر پیدا کنید.

می توان فاصله بین همه جفت نقاط را محاسبه کرد که از آنها n (n-1) / 2 وجود دارد ، سپس جفت را با کمترین فاصله انتخاب کنید. این الگوریتم بی رحمانه زمان O ( n 2 ) را می گیرد. یعنی زمان اجرای آن متناسب با مربع تعداد نقاط است. یک نتیجه کلاسیک در هندسه محاسباتی ، فرمول یک الگوریتم است که O ( n log n ) را انجام می دهد. الگوریتم های تصادفی شده که O ( n ) را انتظار می رود ، [3] و همچنین یک الگوریتم قطعی که زمان O ( n log log n ) را به طول می انجامد ، [4] نیز کشف شده است.

کلاس های مشکل [ ویرایش ]

مشکلات اساسی در هندسه محاسباتی با توجه به معیارهای مختلف ممکن است به روشهای مختلفی طبقه بندی شود. کلاسهای عمومی زیر ممکن است از هم تفکیک شوند.

مشکلات استاتیک [ ویرایش ]

در مشکلات این دسته ، مقداری ورودی داده می شود و خروجی مربوطه نیز احداث یا یافت می شود. برخی از مشکلات اساسی از این نوع عبارتند از:

پیچیدگی محاسباتی برای این دسته از مشکلات با زمان و مکانی (حافظه رایانه) مورد نیاز برای حل یک مثال مشکل خاص برآورد می شود.

مشکلات پرس و جو هندسی [ ویرایش ]

در مشکلات پرس و جو هندسی ، معمولاً به عنوان مشکلات جستجوی هندسی شناخته می شود ، ورودی از دو بخش تشکیل می شود: قسمت فضای جستجو و بخش پرس و جو که نسبت به نمونه های مسئله متفاوت است. فضای جستجو به طور معمول نیاز به پردازش دارد ، به گونه‌ای که به چندین سؤال پاسخ داده شود.

برخی از مشکلات اساسی پرس و جو هندسی عبارتند از:

  • جستجوی محدوده : مجموعه ای از نقاط را به دست بیاورید تا بتوانید تعداد نقاط موجود در یک منطقه پرس و جو را بطور موثر شمارش کنید.
  • موقعیت مکانی : با توجه به پارتیشن بندی فضای موجود در سلول ها ، یک ساختار داده را تولید کنید که به طرز کارآمد می گوید نقطه پرس و جو در کدام سلول قرار دارد.
  • نزدیکترین همسایه : مجموعه ای از نقاط را پردازش کنید تا به طور مؤثر دریابید که کدام نقطه نزدیک به یک نقطه پرس و جو است.
  • ردیابی ری : با توجه به مجموعه ای از اشیاء موجود در فضا ، یک ساختار داده را تولید کنید که به طور موثر می گوید که ابتدا یک پرتوی کوئری از کدام شیء عبور می کند.

اگر فضای جستجو ثابت باشد ، پیچیدگی محاسباتی برای این دسته از مشکلات معمولاً توسط:

  • زمان و مکان مورد نیاز برای ساختن ساختار داده ای که باید در آن جستجو شود
  • زمان (و گاهی اوقات فضای اضافی) برای پاسخ به سؤالات.

برای این مورد که فضای جستجو مجاز است متفاوت باشد ، به " مشکلات پویا " مراجعه کنید.

مشکلات پویا [ ویرایش ]

کلاس بزرگ دیگر مشکلات پویا است که در آن هدف پیدا کردن یک الگوریتم کارآمد برای پیدا کردن یک راه حل به طور مکرر پس از هر اصلاح افزایشی داده های ورودی (اضافه یا حذف عناصر هندسی ورودی) است. الگوریتم های مربوط به مشکلات از این نوع به طور معمول شامل ساختار داده های پویا هستند . هر یک از مشکلات هندسی محاسباتی ممکن است با هزینه افزایش زمان پردازش به یک پویا تبدیل شود. به عنوان مثال ، ممکن است مشکل جستجوی دامنه با ارائه موارد اضافی و یا حذف نقاط به مشکل جستجوی محدوده پویا تبدیل شود . بدنه محدب پویا مشکل این است که از پوسته محدب پیگیری کنید ، به عنوان مثال ، برای مجموعه پویا در حال تغییر از نقاط ، به عنوان مثال ، در حالی که نقاط ورودی درج یا حذف شده است.

پیچیدگی محاسباتی برای این دسته از مشکلات توسط:

  • زمان و مکان مورد نیاز برای ساختن ساختار داده ای که باید در آن جستجو شود
  • زمان و مکان برای تغییر ساختار داده جستجو شده پس از تغییر افزایشی در فضای جستجو
  • زمان (و گاهی اوقات یک فضای اضافی) برای پاسخ به یک سؤال.

تغییرات [ ویرایش ]

بسته به متن ممکن است برخی از مشکلات به عنوان متعلق به هر یک از دسته ها تلقی شوند. برای مثال ، مشکل زیر را در نظر بگیرید.

  • نقطه در چند ضلعی : تصمیم بگیرید که یک نقطه در یک ضرب چند قطعه در داخل یا خارج باشد.

در بسیاری از برنامه های کاربردی ، این مشکل به عنوان یک تخته ، یعنی متعلق به طبقه اول ، درمان می شود. به عنوان مثال ، در بسیاری از برنامه های گرافیکی رایانه یک مشکل رایج این است که دریابید که کدام ناحیه بر روی یک نشانگر کلیک می کند . با این حال ، در برخی از برنامه ها ، چند ضلعی مورد نظر تغییر ناپذیر است ، در حالی که نقطه بیانگر یک پرس و جو است. به عنوان مثال ، چند ضلعی ورودی ممکن است مرز یک کشور را نشان دهد و یک نقطه موقعیت یک هواپیما باشد و مشکل این است که تعیین کنیم هواپیما مرز را نقض کرده یا خیر. سرانجام ، در مثال قبلی که در مورد گرافیک های رایانه ای ذکر شد ، در برنامه های CAD ، داده های ورودی در حال تغییر اغلب در ساختار داده های پویا ذخیره می شوند ، که ممکن است برای سرعت بخشیدن به نمایش داده های چند ضلعی مورد سوء استفاده قرار بگیرد.

در بعضی از زمینه های مشکلات پرس و جو انتظارات معقولی نسبت به توالی نمایش داده ها وجود دارد که ممکن است برای ساختار داده های کارآمد یا برآورد پیچیدگی محاسباتی محکم تر مورد سوء استفاده قرار بگیرد. به عنوان مثال ، در بعضی موارد شناختن بدترین حالت برای کل زمان برای کل دنباله N نمایش داده ها مهم است ، نه برای یک پرس و جو واحد. همچنین به " تحلیل مستهجن " مراجعه کنید .

هندسه محاسباتی عددی [ ویرایش ]

مقاله اصلی: طراحی هندسی به کمک رایانه

این شاخه همچنین به عنوان مدل سازی هندسی و طراحی هندسی به کمک رایانه (CAGD) شناخته می شود.

مشکلات اصلی منحنی و مدل سازی سطح و نمایندگی است.

مهمترین ابزارها در اینجا منحنی های پارامتری و سطوح پارامتری از قبیل منحنی های بزیر ، منحنی های اسپلین و سطوح هستند. روش غیر پارامتری مهم روش تنظیم سطح است .

مناطق کاربردی هندسه محاسباتی شامل کشتی سازی ، هواپیما و صنایع خودرو است.