Designing a metaheuristic mining algorithm to separate two-color points in a two-dimensional environment

  • Parisa Aghazade MSC student of Islamic Azad University, North Tehran Branch, Tehran, Iran
  • Alireza Bagheri Assistant professor and faculty member of Amirkabir University
  • Mohamadmansoor Riahi Kashani Assistant professor and faculty member, Islamic Azad University, North Tehran University, Tehran, Iran

Resumen

The separation of color points is one of the important issues in computational geometry, which is used in various parts of science; it can be used in facility locating, image processing and clustering. Among these, one of the most widely used computational geometry in the real-world is the problem of covering and separating points with rectangles. In this paper, we intend to consider the problem of separating the two-color points sets, using three rectangles. In fact, our goal is to separate desired blue points from undesired red points by three rectangles, in such a way that these three rectangles contain the most desire points. For this purpose, we provide a metaheuristic algorithm based on the simulated annealing method that could separates blue points from input points, , in time order O (n) with the help of three rectangles. The algorithm is executed with C# and also it has been compared and evaluated with the optimum algorithm results. The results show that our recommended algorithm responses is so close to optimal responses, and also in some cases we obtains the exact optimal response.

Citas

1. Hanabadi Farahani, Afsaneh. (2013), "providing algorithms for separating color points with some geometric shapes," Master thesis, Faculty of Computer engineering, North Tehran University, Tehran.
2. Moslehi, Zahra. (2012), "Separability of points with geometric objects in two dimensional space," Master thesis, Faculty of Computer Engineering and Information Technology, Amir Kabir University, Tehran.
3. Khalafi, Sarah (2013), "An algorithm for the separation of points within polygonal environments using the minimum number of distinctive chord" Master thesis, Faculty of computer engineering, North Tehran University, Tehran.
4. Sheikhi, F. (2010), "Covering points in the Page Using Geometric Shapes," Master thesis, Faculty of Computer Engineering and Information Technology, Amir Kabir University, Tehran.
5. Mitsunori Miki, Satoru Hiwat, Tomoyuki Hiroyasu,(2006), "Simulated Annealing using an Adaptive Search Vector", 1-4244-0023-2006 IEEE.
6. Sylvester J.J., (2008), “A question in the geometry of situation”, Quart. J. of Math. 1 (1857) 79.
7. Segal M. and Kedem K., (1998), "Enclosing k points in the smallest axis parallel rectangle", , Information Processing Letters, vol. 65, no. 2, pp. 95-99. https://doi.org/10.1016/S0020-0190(97)00212-3
8. Seara C., (2002), "Geometric separability", in Applied Mathematics, Ph.D. Thesis, Universitat Polit'ecnica de Cataluny.
9. Armaselu B. and Daescu O., (2016), "Dynamic minimum bichromatic separating circle", Theoretical Computer Science. https://doi.org/10.1007/978-3-319-26626-8_50
10. De Pano N.A.A., (1987), “Rotating calipers revisited: optimal polygonal enclosures in optimal time”, ACM South Central Reginal Conf., Lafayette LA.
11. Freeman H. and Shapria R., (1975), "Determining the minimum area enclosing rectangle for an arbitrary closed curve", Commun. of the ACM 18, pp. 409-413. https://doi.org/10.1145/360881.360919
12. Eckstein J., Hammer P . L., Liu Y ., Nediak M. and Simeone B., (1992), "Finding minimum area kgons", Discrete & Computational Geometry (DCG), vol. 7, pp. 45-58. https://doi.org/10.1007/BF02187823
13. Khalafi Sara, Bagheri Alireza, Riahi Kashani M. M., (2014), "Finding The Biggest Monochromatic Polygon", INTERNATIONAL JOURNAL OF Scientific & Technology Research Volume 3, Issue 3.
14. Moslehi Zahra, Bagheri Alireza, (2016), "Separating bichromatic point sets by two disjoint isothetic rectangles", Scientia Iranica D. https://doi.org/10.24200/sci.2016.3891
Publicado
2019-10-25
Cómo citar
Aghazade , P., Bagheri , A., & Kashani , M. R. (2019). Designing a metaheuristic mining algorithm to separate two-color points in a two-dimensional environment. Revista Innovaciencia , 7(2). https://doi.org/10.15649/2346075X.773
Sección
Artículo de investigación científica y tecnológica