بتا اسکلت

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
بتا اسکلت 1.1 مبتنی بر دایره (یال‌های ضخیم و پررنگ) و بتا اسکلت 0.9 ( یال‌های خط‌چین و نازک) برای 100 نقطه‌ی تصادفی در یک مربع.

در هندسه‌ی محاسباتی و نظریه‌ی گراف هندسی، بتا اسکلت یک گراف بدون جهت است که برروی مجموعه‌ای از نقاط هندسه‌ی اقلیدسی تعریف می‌شود. دو نقطه‌ی p و q در صورتی توسط یک یال به یکدیگر متصل می‌شوند که همه‌ی زاویه‌های prq از آستانه‌ی تعیین شده توسط پارامتر عددی β کمتر باشد.

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

ناحیه‌های خالی Rpq که اسکلت بتا مبتنی بر دایره را تعریف می‌کنند. سمت چپ: β <1. وسط: β =1. سمت راست: β> 1

اگر β یک عدد حقیقی مثبت باشد، زاویه‌ی θ با استفاده از فرمول زیر بدست می‌آید:

\theta = \begin{cases} \sin^{-1} \frac{1}{\beta}, & \text{if }\beta \ge 1 \\ \pi - \sin^{-1}{\beta}, & \text{if }\beta\le 1\end{cases}

برای هر دو نقطه‌ی p و q در صفحه، Rpq را مجموعه‌ای از نقاط در نظر بگیرید به طوری‌که زاویه‌ی prq از θ بزرگتر باشد. در این صورت به ازای β ≥ 1 و θ ≤ π/2 مجموعه‌ی Rpq به صورت اجتماع دو دایره با اندازه‌ی قطر βd(p,q) در خواهد آمد و به ازای β ≤ 1 و θ ≥ π/2 مجموعه‌ی Rpq به صورت اشتراک دو دایره به قطر d(p,q)/β خواهد شد. در صورتی که β = 1 باشد هر دو فرمول بالا جواب θ = π/2 را خواهند داد و مجموعه‌ی Rpq به صورت یک دایره به قطر pq خواهد شد.

اگر S یک مجموعه‌ی مجزا از نقاط در صفحه‌ی هندسه‌ی اقلیدسی باشد، بتا اسکلت آن یک گراف بدون جهت است که در آن دو نقطه‌ی p و q در صورتی با یال pq به یکدیگر متصل می‌شوند که Rpq حاوی هیچ یک از نقاط مجموعه‌ی S نباشد. در حقیقت بتا اسکلت یک گراف ناحیه خالی می‌باشد که با ناحیه‌های Rpq تعریف شده‌اند.[۱] هنگامی که مجموعه‌ی S شامل نقطه‌ی r باشد به طوری‌که زاویه‌ی prq بزرگتر از θ باشد، pq یال بتا اسکلت نخواهد بود؛ بتا اسکلت شامل آن جفت pq هایی می‌باشد که همچین نقطه‌ی r ای برای آن‌ها وجود نداشته باشد.

تعریف مبتنی بر هلال[ویرایش]

بعضی از نویسنده‌ها تعریف دیگری را بیان می‌کنند که در آن ناحیه‌های خالی Rpq به ازای β > 1 اجتماع دو دایره نیستند بلکه عدسی می‌باشند (در این متن به آن‌ها هلال می‌گوییم )، یعنی اشتراک دو دایره‌ی متناجس به قطر βd(p,q) هستند به طوری‌که پاره خط pq برروی شعاع هر دو دایره قرار می‌گیرد و همچنین دو نقطه‌ی p و q روی مرز تقاطع دایره‌ها قرار خواهند گرفت. همانند تعریف مبتنی بر دایره، بتا اسکلت مبتنی بر هلال نیز، در صورتی دارای یال pq می‌باشد که ناحیه‌ی Rpq از نقاط دیگر خالی باشد. با توجه به این تعریف، گراف همسایه‌ی مرتبط یک حالت خاص از بتا اسکلت با β = 2 می‌باشد. هر دو تعریف مبتنی بر دایره و مبتنی بر هلال به ازای β ≤ 1 یکسانند اما برای مقادیر بزرگ‌تر β، تعریف بتا اسکلت مبتنی بر دایره زیر گرافی از بتا اسکلت مبتنی بر هلال می‌باشد.

یک تفاوت مهم میان بتا اسکلت مبتنی بر دایره و هلال در این است که به ازای هر مجموعه نقاطی که روی یک خط قرار نداشته باشند، همیشه یک مقدار به اندازه‌ی کافی بزرگ برای β وجود دارد که بتا اسکلت مبتنی بر دایره‌ی آن یک گراف تهی باشد. در مقابل اگر یک جفت نقاط p و q دارای این ویژگی باشند که برای همه‌ی نقاط r دیگر، یکی از دو زاویه‌ی pqr و qpr منفرجه شود، در آن صورت بدون توجه به این‌که β چقدر بزرگ باشد بتا اسکلت مبتنی بر هلال حتماً حاوی یال pq خواهد بود.

تاریخچه[ویرایش]

بتا اسکلت اولین بار توسط Kirkpatrick & Radke (1985) به عنوان یک گونه‌ی مستقل از مقیاس از شکل‌های آلفای Edelsbrunner, Kirkpatrick & Seidel (1983) مطرح شد. نام “بتا اسکلت” به این علت ایجاد شده است که بتا اسکلت از بعضی جهات شکل یک مجموعه نقاط را شرح می‌دهد به همان طریقی که اسکلت توپولوژی شکل ناحیه‌های دوبعدی را بیان می‌کند. انواع بسیار دیگری از گراف‌های بتا اسکلت وجود دارند که با ناحیه‌های خالی دیگر تعریف می‌شوند.[۱][۲]

ویژگی‌ها[ویرایش]

اگر β به صورت پیوسته از 0 تا ∞ تغییر کند، β-اسکلت‌های مبتنی بر دایره دنباله‌ای از گراف‌ها را، از گراف کامل تا گراف تهی، تشکیل می‌دهند. حالت خاصّ β=1 گراف گابریل را نتیجه می‌دهد که شامل درخت پوشای کمینه‌ی اقلیدسی است. بنابراین، زمانی که β≤1، یک β-اسکلت شامل گراف گابریل و درخت پوشای کمینه هم هست.

برای هر β ثابت، می‌توان از یک ساختار فراکتال که نمایانگر نسخه‌ی مسطح برف‌دانه‌ی کخ باشد برای مشخص کردن دنباله‌ای از گروه نقطه‌ها که β-اسکلت‌های آن‌ها مسیرهایی به طول دلخواه در یک مربع واحد است، استفاده کرد. بنابراین، برخلاف مسئله‌ی مرتبطِ مثلث‌بندی دیلانی، β-اسکلت‌ها پوشای هندسی نیستند.[۳]

الگوریتم‌ها[ویرایش]

یک الگوریتم بدیهی که برای هر سه‌تایی q، p و r عضویت r را در محدوده‌ی R_{pq} بررسی می‌کند، می‌تواند برای هر مجموعه‌ی nتایی از نقاط، β-اسکلت را در زمان O(n^3) بسازد.

به ازای β≥1، یک β-اسکلت (با هر یک از تعریف‌ها) زیرگرافی از گراف گابریل است که آن هم زیرگرافی از مثلث‌بندی دیلانی است. اگر pq یکی از یال‌های مثلث‌بندی دیلانی باشد که به β-اسکلت تعلق ندارد، آن‌گاه نقطه‌ی r، یکی از دو نقطه‌ای که در مثلث‌بندی دیلانی با p و q تشکیل مثلث می‌دهند، زاویه‌ی بزرگ prq را درست می‌کند. در نتیجه، برای این مقادیر β، یک β-اسکلت مبتنی بر دایره با محاسبه‌ی مثلث‌بندی دیلانی و حذف کردن یال‌های اضافی با این آزمون برای یک مجموعه‌ی شامل n نقطه در زمان O(nlogn) ساخته می‌شود. [۲]

به ازای β<1 الگوریتم دیگری از Hurtado, Liotta & Meijer (2003) ساختن β-اسکلت را در زمان O(n^2) ممکن می‌سازد. کران بالای بهتری برای زمان اجرا در بدترین حالت ممکن نیست. زیرا برای هر مقدار ثابت β در محدوده‌ی ۰ تا ۱، در حالت کلی مجموعه‌هایی از نقاط وجود دارند که β-اسکلت آن‌ها یک گراف کامل است که تعداد یال‌هایش با توان دوم تعداد نقاط متناسب است. همچنین تمام طیف β (دنباله‌ی β-اسکلت‌های مبتنی بر دایره که از تغییر مقدار β به‌دست می‌آیند) در زمان مشابه (درجه‌ی دو) محاسبه می‌شود.

کاربردها[ویرایش]

از β-اسکلت مبتنی بر دایره می‌توان در آنالیز تصویر برای بازسازی شکل یک شیء دو بعدی با داشتن مجموعه‌ای از نقاط نمونه روی مرز آن شیء استفاده کرد.(شکل محاسباتی بازی وصل کردن نقاط، که در آن ترتیب نقطه‌ها در صورت مسئله نیست و باید توسط یک الگوریتم به دست آید.) اگرچه برای این کار باید مقدار مناسبی برای پارامتر β اتخاذ شود، ثابت می‌شود به ازای β=1.7، در صورتی که نسبت تراکم نمونه‌ها به انحنای موضعی سطح به اندازه‌ی کافی زیاد باشد، β-اسکلت تمام مرز هر سطح صاف را بازسازی می‌کند و هیچ یال اضافی‌ای تولید نمی‌کند. [۴] البته در عمل، مقدار β=1.2 در یک سامانه اطلاعات جغرافیایی برای بازسازی نقشه‌ی خیابان‌ها از روی مجموعه‌ای از نقاط که روی خط میانی خیابان‌ها بودند مناسب‌تر بود. [۵] برای حالت‌های تعمیم‌یافته‌ی روش β-اسکلت برای بازسازی سطوح در سه بعد، Hiyoshi (2007) را ببینید.

از β-اسکلت‌های مبتنی بر دایره برای یافتن زیرگراف‌های مثلث‌بندی با وزن کمینه‌ی یک مجموعه از نقاط استفاده می‌شود: برای مقادیر به اندازه‌ی کافی بزرگ β، هر یال β-اسکلت به مثلث‌بندی با وزن کمینه تعلق دارد. اگر نقاط ورودی با این یال‌ها یک گراف همبند را تشکیل دهند، یال‌های باقی‌مانده‌ی مثلث‌بندی با وزن کمینه با برنامه‌نویسی پویا در زمان چندجمله‌ای به دست می‌آیند. البته مسئله‌ی مثلث‌بندی با وزن کمینه در حالت کلی ان‌پی-سخت است و یال‌های به دست آمده با این روش الزاماً یک گراف همبند درست نمی‌کنند.[۶]

علاوه بر این، β-اسکلت‌ها در یادگیری ماشین برای حلّ مسائل شناسایی هندسی [۷] و در شبکه‌های بی‌سیم ادهاک به عنوان یک سازوکار برای کنترل پیچیدگی ارتباط، با انتخاب یک زیرمجموعه از جفت ایستگاه‌های بی‌سیم که توانایی ارتباط با یک‌دیگر را دارند، کاربرد دارند. [۸]

پانوشت‌ها[ویرایش]

منابع[ویرایش]

  • مشارکت‌کنندگان ویکی‌پدیا، «Beta skeleton»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۱۱ دسامبر ۲۰۱۳).