بتا اسکلت

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

تعریف مبتنی بر دایره

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

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

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

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

تعریف مبتنی بر هلال

بعضی از نویسنده‌ها تعریف دیگری را بیان می‌کنند که در آن ناحیه‌های خالی R_pq به ازای β > 1 اجتماع دو دایره نیستند بلکه عدسی می‌باشند (در این متن به آن‌ها هلال می‌گوییم )، یعنی اشتراک دو دایرۀ متناجس به قطر βd(p,q) هستند به‌طوری‌که پاره خط pq بر روی شعاع هر دو دایره قرار می‌گیرد و همچنین دو نقطۀ p و q روی مرز تقاطع دایره‌ها قرار خواهند گرفت. همانند تعریف مبتنی بر دایره، بتا اسکلت مبتنی بر هلال نیز، در صورتی دارای یال pq می‌باشد که ناحیۀ R_pq از نقاط دیگر خالی باشد. با توجه به این تعریف، گراف همسایۀ مرتبط یک حالت خاص از بتا اسکلت با β = 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) را ببینید.

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

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

پانوشت‌ها

↑ ^۱٫۰ ^۱٫۱ (Cardinal، Collette و Langerman 2009).
↑ ^۲٫۰ ^۲٫۱ (Veltkamp 1992).
↑ (Eppstein 2002); (Bose و دیگران 2002); (Wang و دیگران 2003).
↑ (Amenta، Bern و Eppstein 1998); (O'Rourke 2000).
↑ (Radke و Flodmark 1999).
↑ (Keil 1994); (Cheng و Xu 2001).
↑ (Zhang و King 2002); (Toussaint 2005).
↑ (Bhardwaj، Misra و Xue 2005).

منابع

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

Amenta, Nina; Bern, Marshall; Eppstein, David (1998), "The crust and the beta-skeleton: combinatorial curve reconstruction", Graphical Models & Image Processing, 60/2 (2): 125–135, archived from the original on 22 March 2006, retrieved 11 December 2013.
Bhardwaj, Manvendu; Misra, Satyajayant; Xue, Guoliang, "Distributed topology control in wireless ad hoc networks using ß-skeleton", Workshop on High Performance Switching and Routing (HPSR 2005), Hong Kong, China (PDF), archived from the original (PDF) on 7 June 2011, retrieved 11 December 2013.
Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David G. (2002), "On the spanning ratio of Gabriel graphs and β-skeletons", LATIN 2002: Theoretical Informatics, Lecture Notes in Computer Science, vol. 2286, Springer-Verlag, pp. 77–97, doi:10.1007/3-540-45995-2_42.
Cardinal, Jean; Collette, Sébastian; Langerman, Stefan (2009), "Empty region graphs", Computational Geometry Theory & Applications, 42 (3): 183–195, doi:10.1016/j.comgeo.2008.09.003.
Cheng, Siu-Wing; Xu, Yin-Feng (2001), "On β-skeleton as a subgraph of the minimum weight triangulation", Theoretical Computer Science, 262 (1–2): 459–471, doi:10.1016/S0304-3975(00)00318-2.
Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund (1983), "On the shape of a set of points in the plane", IEEE Transactions on Information Theory, 29 (4): 551–559, doi:10.1109/TIT.1983.1056714.
Eppstein, David (2002), "Beta-skeletons have unbounded dilation", Computational Geometry Theory & Applications, 23 (1): 43–52, arXiv:cs.CG/9907031, doi:10.1016/S0925-7721(01)00055-4.
Hiyoshi, H. (2007), "Greedy beta-skeleton in three dimensions", Proc. 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007), pp. 101–109, doi:10.1109/ISVD.2007.27.
Hurtado, Ferran; Liotta, Giuseppe; Meijer, Henk (2003), "Optimal and suboptimal robust algorithms for proximity graphs", Computational Geometry Theory & Applications, 25 (1–2): 35–49, doi:10.1016/S0925-7721(02)00129-3.
Keil, J. Mark (1994), "Computing a subgraph of the minimum weight triangulation" (PDF), Computational Geometry Theory & Applications, 4 (1): 18–26, doi:10.1016/0925-7721(94)90014-0^{^{[پیوند مرده]}}.
Kirkpatrick, David G.; Radke, John D. (1985), "A framework for computational morphology", Computational Geometry, Machine Intelligence and Pattern Recognition, vol. 2, Amsterdam: North-Holland, pp. 217–248.
O'Rourke, Joseph (2000), "Computational Geometry Column 38", SIGACT News, 31 (1): 28–30, arXiv:cs.CG/0001025, doi:10.1145/346048.346050.
Radke, John D.; Flodmark, Anders (1999), "The use of spatial decompositions for constructing street centerlines" (PDF), Geographic Information Sciences, 5 (1): 15–23.
Toussaint, Godfried (2005), "Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining", International Journal of Computational Geometry and Applications, 15 (2): 101–150, doi:10.1142/S0218195905001622.
Veltkamp, Remko C. (1992), "The γ-neighborhood graph" (PDF), Computational Geometry Theory & Applications, 1 (4): 227–246, doi:10.1016/0925-7721(92)90003-B.
Wang, Weizhao; Li, Xiang-Yang; Moaveninejad, Kousha; Wang, Yu; Song, Wen-Zhan (2003), "The spanning ratio of β-skeletons", Proc. 15th Canadian Conference on Computational Geometry (CCCG 2003) (PDF), pp. 35–38.
Zhang, Wan; King, Irwin (2002), "Locating support vectors via β-skeleton technique", Proc. Proceedings of the 9th International Conference on Neural Information Processing (ICONIP'02), Orchid Country Club, Singapore, November 18-22, 2002 (PDF), pp. 1423–1427, archived from the original (PDF) on 3 March 2012, retrieved 11 December 2013.

[ccl-1] ۱٫۰ ^۱٫۱ (Cardinal، Collette و Langerman 2009).

[v-2] ۲٫۰ ^۲٫۱ (Veltkamp 1992).

[3] (Eppstein 2002); (Bose و دیگران 2002); (Wang و دیگران 2003).

[4] (Amenta، Bern و Eppstein 1998); (O'Rourke 2000).

[5] (Radke و Flodmark 1999).

[6] (Keil 1994); (Cheng و Xu 2001).

[7] (Zhang و King 2002); (Toussaint 2005).

[8] (Bhardwaj، Misra و Xue 2005).

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]