Separating Bichromatic Point Sets by Fixed Angle Double Wedges
Subject Areas : electrical and computer engineeringM. Maleki Shahrakiand 1 , A. Bagheri 2 * , M. Nayeri 3
1 -
2 -
3 -
Keywords: Computational geometry covering separation double-wedge algorithm bichromatic point set,
Abstract :
The point-set covering is one of the important problems in computational geometry, which has many applications. In this problem, the given points should be covered by at least one geometric shape. A variant of the problem is the point-set separation, in which there are at least two different kinds of points which are colored by different colors. The geometric shapes, which are called separators, should only cover the points of the same color. In this paper, separation of blue and red points by a double-wedge of a given angle θ is considered. The proposed algorithm reports all separator θ angle double-wedges in optimal time O(nlogn).
[1] J. O'Rourke, Computational Geometry in C, Camb. Univ. Press, 2nd Ed., 1988.
[2] N. Megiddo, "Linear time algorithm for linear programming in R3 and related problems," SIAM J. of Computing, vol. 12, no. 4, pp. 759-776, Nov. 1983.
[3] M. E. Houle and G. Toussaint, "Computing the width of a set," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 10, no. 5, pp. 761-765, Sep. 1988.
[4] J. O'Rourke, A. Aggarwal, S. Maddila, and M. Baldwin, "An optimal algorithm for finding minimal enclosing triangle," J. of Algorithms, vol. 7, no. 2, pp. 258-269, Jun. 1986.
[5] B. K. Bhathacharya and A. Mukhopadhyay, "On the minimum perimeter triangle enclosing a convex polygon," in Proc. Japanese Conf. on Discrete and Computational Geometry, JCDCG'02, 2002.
[6] G. Toussaint, "Solving geometric problems with the rotating calipers," in Proc. IEEE MELECON, 8 pp., May 1983.
[7] S. W. Bae, C. Lee, H. Ahn, S. Choi, and K. Chwa, "Computing minimum-area rectilinear convex hull and L-shape," Comput. Geom.: Theory and Applications, vol. 42, no. 9, pp. 903-912, Nov. 2009.
[8] S. W. Bae, C. Lee, H. Ahn, S. Choi, and K. Chwa, "Maintaining extremal points and its applications to deciding optimal orientions," in Proc. 18th Int. Symp., Algorithms and Computation: ISAAC'07, pp. 788-799, Mar. 2007.
[9] C. Saha and S. Das, "Covering a set of points in a plane using two parallel rectangles," Inf. Process. Lett., vol. 109, no. 16, pp. 907-912, Ju.l 2009.
[10] T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning, Springer-Verlag, Germany, 2001.
[11] N. Megiddo, "Linear-time algorithms for linear programming in R3 and related problem," SIAM J. Comlout., vol. 12, no. 4, pp. 759-776, Nov. 1983.
[12] C. Seara, On Geometric Separability, in Applied Mathematics, Ph.D. Thesis, University of. Polit'ecnica de Catalunya, 2002.
[13] E. M. Arkin, D. Garijo, A. Marquez, J. S. B. Mitchell, and C. Seara, "Separability of point sets by k-level linear classification trees," Int. J. of Computational Geometry & Applications, vol. 22, no. 2, pp. 143-165, Apr. 2012.
[14] E. M. Arkin, F. Hurtado, J. S. B. Mitchell, C. Seara, and S. S. Skiena, "Some lower bounds on geometric separability problems," International J. of Computational Geometry and Applications, vol. 16, no. 1, pp. 1-26, Dec. 2006.
[15] F. Hurtado, M. Noy, P. A. Ramos, and C. Seara, "Separating objects in the plane by wedges and strips," Discrete Applied Mathematics, vol. 199, no. 1-2, pp. 109-138, Apr. 2000.
[16] F. Hurtado, M. Mora, P. A. Ramos, and C. Seara, "Separability by two lines and by nearly-straight polygonal chains," Discrete Applied Mathematics, vol. 144, 1-2, pp. 110-122, Nov. 2004.
[17] F. Hurtado, M. Mora, P. A. Ramos, and C. Seara, "Two problems on separability with lines and polygonals," in Proc. 15th European Workshop on Computational Geometry, pp. 33-35, Nice, France, Feb. 1999.
[18] J. S. B. Mitchell, Approximation Algorithms for Geometric Separating Problems, Technical Report, State University of New York at Stony Brook, 1993.
[19] J. O'Rourke, S. R. Kosaraju, and N. Megiddo, "Computing circular separability," Discrete Comput. Geom., vol. 1, no. 2, pp. 105-113, Jun. 1986.
[20] F. Sheikhi, A. Mohades, and M. Davoodi, "An improved algorithm for finding monochromatic L-shapes in bichromatic point sets," in Proc. of the Contemporary Issues in Computer and Information Sciences, pp. 36-39, Zanjan, Iran, Jan. 2011.
[21] 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, Mar. 2009.
[22] ز. مصلحي، تفکيک‌پذيري نقاط با اشياي هندسي در فضاي دوبعدي، پايان‌نامه کارشناسي ارشد مهندسي کامپيوتر، دانشکده مهندسي کامپيوتر و فناوري اطلاعات، دانشگاه اميركبير، 1391.
[23] ز. مصلحی و ع. ر. باقری، "تفکیک‌پذیری سری نقاط دو رنگ با دو مستطیل مجزا و موازی محورهای مختصات،" مجله علمی- پژوهشی رایانش نرم و فناوری اطلاعات، جلد 1، شماره 2، صص. 42-35، 1391.
[24] J. L. Bentley and T. A. Ottmann, "Algorithms for reporting and counting geometric intersections," IEEE Trans. on Computers, vol. 28, no. 9, pp. 643-647, Sept. 1979.
[25] B. Chazelle and H. Edelsbrunner, "An optimal algorithm for intersecting line segments," J. of the ACM, vol. 39, no. 1, pp. 1-54, Jan. 1992.