Separating Bichromatic Point Sets by Right Triangles
Subject Areas : electrical and computer engineeringAbstract :
Separating colored point sets is an interesting problem in computational geometry with application in machine learning and pattern recognition. In this problem, we are given a geometric shape C and two point sets P and Q of total size n as red and blue points, respectively. Now, we must separate red and blue points by this shape such that all the blue points lie inside it and all the red points lie outside it. In the previous work, we have some algorithms for rectangle and wedge separability but we do not have any algorithm for separating by a triangle and separating by a triangle with a fixed angle such as right triangle. In this paper, we present an efficient algorithm for right triangle seprability. In this algorithm, we use sweep line technique and introduce some events and process them. So, we can report all separating right triangles in O(nlog n) time.
[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.