هندسه محاسباتی

هندسهٔ محاسباتی^[1] یکی از شاخه‌های علوم رایانه است. هندسهٔ محاسباتی علم حل مسائل هندسی به روش الگوریتمی و با استفاده از ساختمان داده‌ها (Data Structures) است. بعضی از مسائل کاملاً هندسی، برآمده از مطالعهٔ الگوریتمهای هندسهٔ محاسباتی است و مطالعه این‌گونه مسائل نیز به عنوان بخشی از هندسهٔ محاسباتی به حساب می‌آیند.

انگیزهٔ اصلی برای قلمداد کردن هندسهٔ محاسباتی به عنوان یک رشتهٔ علمی، پیشرفت در گرافیک رایانه‌ای، طراحی و تولیدات با کمک رایانه (به‌وسیلهٔ نرم‌افزارهایی مانند کد^[2]/کم^[3]) بود؛ ولی طبیعتاً بسیاری از مسائل در هندسهٔ محاسباتی، قدیمی هستند.

کاربردهای مهم دیگر هندسهٔ محاسباتی در دانش روباتیک (برنامه‌ریزی حرکتی)، سیستم‌های اطلاعات جغرافیایی^[4](جستجو و مکان‌یابی هندسی، نقشه‌کشی راه‌ها)، طراحی مدار مجتمع^[5](طراحی و بازبینی هندسی مدارهای مجتمع) و مهندسی با کمک رایانه^[6] (برنامه‌ریزی ماشین‌های کنترل عددی)^[7] است.

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

هندسهٔ محاسباتی ترکیبی (هندسهٔ الگوریتمی): این هندسهٔ محاسباتی اشیای هندسی را به‌عنوان موجودات گسسته در نظر می‌گیرد. براساس کتابی که توسط پرپاراتا^[8] و شاموس^[9] نوشته شده‌است، اصطلاح «هندسهٔ محاسباتی» با این مفهوم، نخستین بار در سال ۱۹۷۵ بیان شده‌است.
هندسهٔ محاسباتی عددی (هندسهٔ ماشینی، طراحی هندسی با کمک رایانه یا مدل‌سازی هندسی): اساس کار این هندسهٔ محاسباتی به این صورت است که اشیای دنیای واقعی را به‌صورت مناسبی برای محاسبات رایانه‌ای در سیستم‌های کد/کم درمی‌آورد. این شاخه ممکن است به‌عنوان هندسهٔ توصیفی پیشرفته در نظر گرفته شود و اغلب یکی از شاخه‌های گرافیک کامپیوتری یا کَد به حساب می‌آید. هندسهٔ محاسباتی با این معنا، از سال ۱۹۷۱ مورد استفاده قرار گرفت.

Remove ads

هدف اصلی از پژوهش در زمینهٔ هندسهٔ محاسباتی ترکیبیاتی این است که، برای حل مسائلی که در زمینه اشیای پایه هندسی (نقاط، خط‌ها، چندضلعی‌ها، چندوجهی‌ها^[10] و…) مطرح می‌شوند، الگوریتم‌ها و ساختارهای دادهٔ^[11] مناسبی تولید شود.

برخی از این مسائل به قدری آسان به نظر می‌رسند که تا زمان پیدایش رایانه‌ها مشکل به حساب نمی‌آمدند. برای مثال به مسئلهٔ نزدیک‌ترین زوج^[12] توجه کنید:

n نقطه در صفحه داریم. دو نقطه‌ای که کمترین فاصله را از یکدیگر دارند، پیدا کنید.

می‌توان فاصلهٔ بین جفت نقطه‌ها، که تعدادشان معلوم هست را پیدا کرد و بعد کوچک‌ترین عدد را انتخاب کرد. این الگوریتم از مرتبهٔ^[13] n^۲ است. منظور این است که زمان اجرایش به مربع تعداد نقاط بستگی دارد. یک نتیجهٔ کلاسیک در هندسهٔ محاسباتی ایجاد الگوریتمی بود که از مرتبهٔ n log n زمان بگیرد. الگوریتم‌های تصادفی که از مرتبهٔ n زمان می‌برند، علاوه بر الگوریتم‌های تعیین‌کننده‌ای که از مرتبهٔ n log n زمان می‌برند نیز کشف شده‌اند.

برای GIS جدید،^[14] گرافیک کامپیوتری و سیستم‌های طراحی مدارهای مجتمع که روزانه ده‌ها و صدها میلیون نقطه را به کار می‌گیرند، تفاوت بین مرتبهٔ n^۲و مرتبهٔ n log n می‌تواند تفاوت بین روزها و ثانیه‌ها محاسبه، باشد. به همین دلیل است که در هندسهٔ محاسباتی تأکید زیادی روی پیچیدگی محاسباتی شده‌است.

انواع سؤالات

مسائل اساسی در هندسهٔ محاسباتی را می‌توان با در نظر گرفتن معیارهای گوناگون، به روش‌های گوناگونی طبقه‌بندی کرد. یکی از این رده‌بندی‌ها در زیر آمده‌است.

مسائل ایستا

در این گروه از مسائل، نوعی ورودی داده می‌شود و خروجی متناسب باید به دست بیاید یا پیدا شود. برخی مسائل اساسی این نوع عبارت‌اند از:

رویه محدب:^[15] تعدادی نقطه داریم، کوچک‌ترین چندضلعی یا چندوجهی محدبی را پیدا کنید که دربرگیرندهٔ همه نقطه‌هاست.
تقاطع پاره خط‌ها:^[16] تقاطع‌های بین تعدادی پاره‌خط را پیدا کنید.
مثلث‌بندی دلونی^[17]
نمودارهای ورونوی:^[18] با دریافت مجموعه‌ای از نقاط، فضا را بر اساس نزدیک‌ترین نقطه تقسیم‌بندی کنید.
برنامه‌ریزی خطی:^[19] برنامه‌ریزی خطی، یا همان بهینه‌سازی خطی، روشی در ریاضیات است که به پیدا کردن مقدار کمینه یا بیشینه از یک تابع خطی روی یک چندضلعی محدب می‌پردازد.
نزدیک‌ترین زوج نقاط:^[20] با دریافت مجموعه‌ای از نقاط، دونقطه‌ای را بیابید که کم‌ترین فاصله را دارند.
کوتاه‌ترین مسیر اقلیدسی:^[21] دو نقطه را در فضای اقلیدسی (با یک مانع چند وجهی) با کوتاه‌ترین مسیر به هم وصل کنید.
مثلث‌بندی چندضلعی:^[22] با دریافت یک چندضلعی، سطح داخل آن را به تعدادی مثلث تقسیم کنید.

پیچیدگی محاسباتی برای این دسته از مسائل براساس زمان و فضای (حافظهٔ کامپیوتری) لازم برای حل مسئله تقریب زده می‌شود.

مسائل جستجوی هندسی

در مسائل جستجوی هندسی^[23] ورودی از دو قسمت تشکیل شده‌است: قسمت فضای جستجو و قسمت جستجو، که در هر مسئله تغییر می‌کند. قسمت فضای جستجو باید به گونه‌ای پیش‌پردازش^[24] شود که بتواند به نحو مطلوبی به سوالات متعدد جواب دهد.

برخی مسائل اساسی جستجوی هندسی عبارت‌اند از:

جستجوی محدوده:^[25] مجموعه‌ای از نقاط را پیش‌پردازش می‌کند برای این‌که درون محدودهٔ مطلوب، تعداد نقاط را بشمارد.
محل‌یابی نقطه:^[26] با دریافت فضایی که تقسیم‌بندی شده، یک ساختار داده تولید می‌کند که به ما می‌گوید نقطهٔ مورد نظر، در کدام قسمت قرار دارد.
نزدیک‌ترین همسایه:^[27] مجموعه‌ای از نقاط را به این منظور پیش‌پردازش می‌کند که تعیین کند کدام نقطه، به نقطهٔ مورد نظر نزدیک‌تر است.
ردیابی پرتو:^[28] با دریافت مجموعه‌ای از اجسام در فضا، یک ساختار داده تولید می‌کند تا تعیین کند که پرتوی جستجوی^[29] مورد نظر، نخستین بار با کدام جسم برخورد می‌کند.

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

زمان و حافظهٔ لازم برای ساختن ساختار داده‌ای که باید در داخل آن جستجو شود.
زمان (و برخی مواقع یک حافظهٔ اضافی) برای پاسخ به جستجوها.

برای حالتی که فضای جستجو تغییر می‌کند، به مسائل پویا^[30] رجوع شود.

مسائل پویا

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

پیچیدگی محاسباتی این دسته از مسائل با توجه به عوامل زیر تخمین زده می‌شود:

زمان و حافظهٔ لازم برای ساختن ساختار داده‌ای که باید در داخل آن جستجو شود.
زمان و حافظهٔ لازم برای تغییر دادن ساختار دادهٔ مورد جستجو، بعد از یک تغییر در فضای جستجو.
زمان (و برخی مواقع یک حافظهٔ اضافی) برای پاسخ به جستجوها.

حالت‌های گوناگون

می‌توان با برخی داده‌ها به گونه‌ای برخورد کرد که با توجه به محتوایشان جزو هر کدام از گروه‌های معرفی شده قرار گیرند. برای مثال، مسئله زیر را در نظر بگیرید: نقطه در چند ضلعی:^[32] مشخص کنید که یک نقطهٔ مورد نظر داخل چند ضلعی است یا خارج آن. در بسیاری از موارد با این مسئله به عنوان یک تک‌تیر^[33] برخورد می‌شود، یعنی این‌که مربوط به گروه اول است. برای مثال، در بسیاری از نمونه‌های گرافیک کامپیوتری یک مسئلهٔ رایج این است که مشخص کند کدام ناحیه از صفحه توسط نشانه‌گر ماوس^[34] کلیک شده‌است. اما در برخی موارد چند ضلعی مورد نظر تغییرناپذیر است در حالی که نقطه مورد جستجو را به نمایش می‌گذارد. برای مثال، چند ضلعی وارد شده می‌تواند نمایندهٔ مرز یک کشور باشد و نقطه، مکان یک هواپیما و مسئله تعیین کردن این است که آیا هواپیما از مرز عبور کرده‌است یا نه. در نهایت، در مثال‌های بیان شده در گرافیک کامپیوتری ورودی‌های متغیر در ساختارهای دادهٔ پویا ذخیره می‌شوند، تا به حل سوالاتی که مربوط به نقاط داخل چندضلعی است، سرعت بخشد.

Remove ads

این شاخه به مدل‌سازی هندسی و طراحی هندسی با کمک کامپیوتر^[35] نیز معروف است و اغلب تحت کلیدواژهٔ^[36] منحنی‌ها و سطح‌ها دیده می‌شود. مسئله‌های اصلی در این نوع از هندسهٔ محاسباتی، مدل‌سازی و ارائهٔ منحنی و سطح است.

در این‌جا مهم‌ترین ابزارها، منحنی‌های پارامتری^[37] و سطح‌های پارامتری^[38] هستند، مانند خم‌های بزیر،^[39] خم‌ها و سطح‌های نواری.^[40] از مهم‌ترین روش‌های غیرپارامتری، روش تنظیم رده^[41] است.

از نخستین و مهم‌ترین کاربردهای هندسهٔ محاسباتی عددی، کاربرد در کشتی‌سازی، هواپیماسازی و صنایع ماشین‌آلات است. اما امروزه، به دلیل حضور گستردهٔ رایانه‌ها و پیشرفته‌تر شدن آن‌ها حتی جعبه‌های عطر و شامپو نیز با تکنیک‌هایی که برای کشتی‌سازان دههٔ ۱۹۶۰ ناشناخته بود طراحی می‌شوند.

Remove ads

مجلات

هندسهٔ محاسباتی الگوریتمی/ترکیبی

در پیوند زیر:

مجلات در زمینهٔ الگوریتم‌های هندسی

فهرستی از مجله‌های معتبر که در زمینهٔ الگوریتم‌های هندسی، پژوهش‌هایی را چاپ کرده‌اند، آمده‌است. توجه شود که با آمدن مجله‌هایی که به هندسهٔ محاسباتی اختصاص یافته‌اند، سهم انتشارات هندسی در مجله‌های علوم کامپیوتر با هدف عمومی و مجله‌های گرافیک کامپیوتری کاهش یافت.

مدل‌سازی هندسی/طراحی هندسی به کمک کامپیوتر

فهرست مجلات در زمینهٔ مدلسازی هندسی

کتاب‌ها

منابع لاتین

1. M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications, 3rd edition, Springer, ۲۰۰۸.

2. .2011,Satyan L. Devadoss, Joseph O'Rourke, Discrete and Computational Geometry, Princeton University

3. J. O'Rourke, Computational Geometry in C, 2nd edition, Cambridge University Press, ۱۹۹۸

منابع فارسی

۱. هندسهٔ محاسباتی: الگوریتم‌ها و کاربردها (ویراست سوم)، تألیف: مارک دی برگ، اوتفرید چیونگ، مارک وان کریولد، مارک اُورمارس- ترجمه: مهدی ایمان‌پرست، انتشارات دانش نگار، تهران، چاپ اول، ۱۳۹۴.

Remove ads

[1]
computational geometry
[2]
CAD
[3]
CAM
[4]
geographic information systems(GIS)
[5]
integrated circuit (IC)
[6]
computer-aided engineering(CAE)
[7]
numerically controlled(NC)
[8]
Preparata
[9]
Shamos
[10]
polyhedra
[11]
data structures
[12]
closest pair problem
[13]
Order (O)
[14]
modern GIS
[15]
Convex hull
[16]
Line segment intersection
[17]
Delaunay triangulation
[18]
Voronoi diagram
[19]
Linear programming
[20]
Closest pair of points
[21]
Euclidean shortest path
[22]
Polygon triangulation
[23]
geometric query problems, geometric search problems
[24]
preprocess
[25]
Range searching
[26]
Point location
[27]
Nearest neighbor
[28]
Ray tracing
[29]
query ray
[30]
Dynamic problems
[31]
dynamic data structures
[32]
point in polygon
[33]
single-shot
[34]
mouse curser
[35]
computer-aided geometric design (CAGD)
[36]
keyword
[37]
parametric curves
[38]
parametric surfaces
[39]
Bezier curves
[40]
spline
[41]
level set method

Remove ads

ایران سازه (انگلیسی) https://web.archive.org/web/20131215134129/http://www.iransaze.com/article-print-841.html
مشارکت‌کنندگان ویکی‌پدیا. «Computational geometry». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲ مه ۲۰۱۱.

[1] [1]
computational geometry

[2] [2]
CAD

[3] [3]
CAM

[4] [4]
geographic information systems(GIS)

[5] [5]
integrated circuit (IC)

[6] [6]
computer-aided engineering(CAE)

[7] [7]
numerically controlled(NC)

[8] [8]
Preparata

[9] [9]
Shamos

[10] [10]
polyhedra

[11] [11]
data structures

[12] [12]
closest pair problem

[13] [13]
Order (O)

[14] [14]
modern GIS

[15] [15]
Convex hull

[16] [16]
Line segment intersection

[17] [17]
Delaunay triangulation

[18] [18]
Voronoi diagram

[19] [19]
Linear programming

[20] [20]
Closest pair of points

[21] [21]
Euclidean shortest path

[22] [22]
Polygon triangulation

[23] [23]
geometric query problems, geometric search problems

[24] [24]
preprocess

[25] [25]
Range searching

[26] [26]
Point location

[27] [27]
Nearest neighbor

[28] [28]
Ray tracing

[29] [29]
query ray

[30] [30]
Dynamic problems

[31] [31]
dynamic data structures

[32] [32]
point in polygon

[33] [33]
single-shot

[34] [34]
mouse curser

[35] [35]
computer-aided geometric design (CAGD)

[36] [36]
keyword

[37] [37]
parametric curves

[38] [38]
parametric surfaces

[39] [39]
Bezier curves

[40] [40]
spline

[41] [41]
level set method

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

هندسه محاسباتی

انواع سؤالات

مسائل ایستا

مسائل جستجوی هندسی

مسائل پویا

حالت‌های گوناگون

مجلات

هندسهٔ محاسباتی الگوریتمی/ترکیبی

مدل‌سازی هندسی/طراحی هندسی به کمک کامپیوتر

کتاب‌ها

منابع لاتین

منابع فارسی

Wikiwand in your browser!

هندسه محاسباتی

انواع سؤالات

مسائل ایستا

مسائل جستجوی هندسی

مسائل پویا

حالت‌های گوناگون

مجلات

هندسهٔ محاسباتی الگوریتمی/ترکیبی

مدل‌سازی هندسی/طراحی هندسی به کمک کامپیوتر

کتاب‌ها

منابع لاتین

منابع فارسی

Wikiwand in your browser!

هندسهٔ محاسباتی ترکیبیاتی

هندسهٔ محاسباتی عددی

مطالعهٔ بیشتر

پانوشت‌ها

منابع