تفکیک‌پذیری مجموعه نقاط دورنگ با مثلث قائم‌الزاویه
الموضوعات :
1 - دانشگاه صنعتی امیرکبیر
2 - دانشگاه صنعتی امیرکبیر
الکلمات المفتاحية: هندسه محاسباتی تفکیک‌پذیری سری نقاط دورنگ مثلث قائم‌الزاویه یادگیری ماشین دسته‌بندی,
ملخص المقالة :
تفکیک‌پذیری نقاط رنگی با اشکال هندسی یکی از مسایل مطرح در هندسه محاسباتی است که کاربردهایی از جمله در یادگیری ماشین و شناسایی الگو دارد. در این مسأله دو سری نقطه P و Q به ترتیب به رنگ‌های قرمز و آبی و به اندازه n در صفحه داده شده است. حال لازم است یک شکل هندسی مشخص را به گونه‌ای در صفحه قرار دهیم که کلیه نقاط آبی را در برگرفته و شامل هیچ نقطه قرمزی نباشد. در کارهای پیشین الگوریتم‌هایی برای تفکیک‌پذیری نقاط با گوه و مستطیل ارائه گردیده ولی تا به حال الگوریتمی برای تفکیک‌پذیری نقاط با یک مثلث و همچنین مثلثی که یک زاویه آن مشخص باشد (مثلاً قائم‌الزاویه) ارائه نشده است. در این مقاله الگوریتمی جدید و کارا برای تفکیک‌پذیری نقاط رنگی با مثلث قائم‌الزاویه ارائه می‌کنیم که قادر خواهد بود با استفاده از راهکار خط جاورب چرخشی، معرفی رخدادها و پردازش آنها در زمان کارای O(nlogn) کلیه مثلث‌های قائم‌الزاویه تفکیک‌کننده را گزارش کند.
[1] C. Seara, On Geometric Separability, in: Applied Mathematics, Ph. D Thesis, University of Politecnica de Catalunya, 2002.
[2] J. S. B. Mitchell, Approximation Algorithms for Geometric Separation Problems, Technical Report, AMS Dept., SUNY Stony Brook, NY, 1993.
[3] D. P. Dobkin and D. Gunopulos, "Geometric problems in machine learning," Lect. Notes in Comput. Sci., vol. 1148, pp. 121-132, 1996.
[4] ز. مصلحی و م. پالهنگ، "دسته‌بندي داده‌هاي دورده‌اي با ابرمستطیل موازي محورهاي مختصات،" پنجمین کنفرانس فناوری اطلاعات و دانش، 7 صص.، شیراز، 1392.
[5] P. L. Hammer, A. Kogan, B. Simeone, and S. Szedmak, "Pareto-Optimal Patterns in Logical Analysis of Data," in RUTCOR Research Report, 2001.
[6] M. Sato and T. Ohtsuki, "Applications of computational geometry to VLSI layout pattern design," INTEGRATION, the VLSI J., vol. 5, no. 3-4, pp. 303-317, Dec. 1987.
[7] M. V. Kreveld, T. V. Lankveld, and R. Veltkamp, "Identifying well-covered minimal bounding rectangles in 2D point data," in Proc. 25th Eur. Workshop on Comput. Geom., pp. 277-280, Belgium, Brussels, 16-18 Mar. 2009.
[8] J. Eckstein, P. Hammer, Y. Liu, M. Nediak, and B. Simeone, "The maximum box problem and its application to data analysis," Comput. Optim. and Appl., vol. 23, no. 3, pp. 85-98, 2002.
[9] J. Backer and M. Keil, "The mono and bichromatic empty rectangle and square problems in all dimensions," in LATIN 2010: Theoretical Informatics, Springer Berlin Heidelberg, vol. 6034, pp. 14-25, App. 2010.
[10] C. Cortes, et al., "Bichromatic separability with two boxes: a general approach," J. of Algorithms, vol. 64, no. 2, pp. 79-88, Feb. 2009.
[11] C. Cortes, J. Diaz-Baoez, and J. Urrutia, "Finding enclosing boxes with empty intersection," in Proc. 23rd Eur. Workshop on Comput. Geom., EWCG'07, pp. 185-188, 19-21 Mar. 2007.
[12] S. Cabello, J. M. Diaz-Banez, C. Seara, J. A. Sellares, J. Urrutia, and I. Ventura, "Covering point sets with two convex objects," in Proc. 21st Eur. Workshop on Comput. Geom., EWCG'05,pp. 179-182, Mar. 2005.
[13] S. Cabello, J. M. Diaz-Banez, C. Seara, J. Urrutia, and I. Ventura, "Covering point sets with two disjoint disks or squares," Comput. Geom.: Theory and Appl., vol. 40, no. 3, pp. 195-206, Aug. 2008.
[14] ز. مصلحی و ع. ر. باقری، "تفکیک‌پذیري سري نقاط دورنگ با دو مستطیل مجزا و موازي محورهاي مختصات،" مجله علمی پژوهشی رایانش نرم و فناوري اطلاعات، جلد 1، شماره 2، صص. 35-42، پاییز 1391.
[15] J. O'Rourke, S. R. Kosaraju, and N. Megiddo, "Computing circular separability," Discrete Comput. Geom., vol. 1, pp. 105-113, 1986.
[16] P. Agarwal, B. Aronov, and V. Koltun, "Efficient algorithms for bichromatic separability," J. of ACM Trans. on Algorithms, vol. 2, no. 2, pp. 209-227, Apr. 2006.
[17] F. Sheikhi, M. de Berg, A. Mohades, and M. Davvodi, "Finding monochromatic l-shapes in bichromatic point sets," in Proc. 22nd Canad. Conf. Comp. Geompp. 269-272, Aug. 2010.
[18] H. Edelsbrunner and F. Preparata, "Minimum polygonal separation," Inf. and Comput., vol. 77, no. 3, pp. 218-232, Jun. 1988.
[19] E. M. Arkin, G. Barequet, and J. S. B. Mitchell, "Algorithms for two box covering," in Proc. 22nd Annu. Symp. on Comput. Geom., pp. 459-467, Jun. 2006.
[20] S. Bespamyatnikh and M. Segal, "Covering a set of points by two axis-parallel boxes," Inf. Process. Lett., vol. 75, no. 3, pp. 95-100, Aug. 2000.
[21] C. Figueiredo and G. Fonseca, "Enclosing weighted points with an almost-unit ball," Inf. Process. Lett., vol. 109, no. 21-22, pp. 1216-1221, Aug. 2009.
[22] P. Mahapatra, P. Goswami, and S. Das, "Maximal covering by two isothetic unit squares," in Proc. of 20th Annual Canad. Conf. Comp. Geom., pp. 103-106, Montreal, Canada, 13-15 Aug. 2008.
[23] P. Bose and J. L. De Carufel, "Minimum-area enclosing triangle with a fixed angle," Comput. Geom., vol. 47, no. 1, pp. 90-109, Jan. 2014.
[24] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications, 3rd Edition, TELOS, Santa Clara, CA, USA, 2008.
[25] B. Chazelle, et al., "Ray shooting in polygons using geodesic triangulations," J. of Algorithmica, vol. 12, no. 1, pp. 54-68, Jul. 1994.
