جداسازی نقاط دو رنگ با دو- گوه با زاویه مشخص
محورهای موضوعی : مهندسی برق و کامپیوترمریم ملکی شهرکی 1 , علیرضا باقری 2 * , مهدیس نیری 3
1 - دانشگاه آزاد اسلامی واحد تهران شمال
2 - دانشگاه صنعتی امیرکبیر
3 - دانشگاه آزاد اسلامی واحد تهران شمال
کلید واژه: هندسه محاسباتي پوشش جداسازي دو- گوه الگوريتم نقاط دو رنگ,
چکیده مقاله :
مسئله پوشش از مسایل مهم و پرکاربرد در هندسه محاسباتي است که در اين مسأله، نقاط بايستي با حداقل يک شکل هندسي پوشانده شوند. نوع خاصي از مسأله پوشش، مسئله جداسازي نقاط است که در اين مسئله حداقل دو دسته نقطه وجود دارد که تمايز آنها با رنگ نشان داده مي‌شود (براي مثال نقاط آبي و قرمز) و بايستي نقاط با يک شکل هندسي از هم جدا شوند که به اين شکل هندسي، جدا‌کننده مي‌گويند. در اين مقاله مسئله جداسازي نقاط آبي و قرمز با دو- گوه جدا‌کننده با زاويه مشخص مورد بررسي قرار مي‌گيرد. الگوريتم ارائه‌شده براي اين مسأله تمام دو- گوه‌هاي جدا‌کننده با زاويه مشخص را در زمان بهينه O (n log n) گزارش مي‌کند.
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.