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

Parisa  Aghazade; Alireza  Bagheri; Mohamadmansoor  Riahi Kashani

doi:10.15649/2346075X.773

Authors

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

DOI:

https://doi.org/10.15649/2346075X.773

Keywords:

Data-mining, Separation of points, Computational geometry, metaheuristic Algorithm, Simulated Annealing (SA).

Abstract

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.

Author Biographies

Parisa Aghazade, MSC student of Islamic Azad University, North Tehran Branch, Tehran, Iran.

MSC student of Islamic Azad University, North Tehran Branch, Tehran, Iran.

Alireza Bagheri, Assistant professor and faculty member of Amirkabir University

Assistant professor and faculty member of Amirkabir University

Mohamadmansoor Riahi Kashani, Assistant professor and faculty member, Islamic Azad University, North Tehran University, Tehran, Iran

Assistant professor and faculty member, Islamic Azad University, North Tehran University, Tehran, Iran

References

Hanabadi Farahani, Afsaneh. (2013), "providing algorithms for separating color points with some geometric shapes," Master thesis, Faculty of Computer engineering, North Tehran University, Tehran.

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.

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.

Sheikhi, F. (2010), "Covering points in the Page Using Geometric Shapes," Master thesis, Faculty of Computer Engineering and Information Technology, Amir Kabir University, Tehran.

Mitsunori Miki, Satoru Hiwat, Tomoyuki Hiroyasu,(2006), "Simulated Annealing using an Adaptive Search Vector", 1-4244-0023-2006 IEEE.

Sylvester J.J., (2008), “A question in the geometry of situation”, Quart. J. of Math. 1 (1857) 79.

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

Seara C., (2002), "Geometric separability", in Applied Mathematics, Ph.D. Thesis, Universitat Polit'ecnica de Cataluny.

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

De Pano N.A.A., (1987), “Rotating calipers revisited: optimal polygonal enclosures in optimal time”, ACM South Central Reginal Conf., Lafayette LA.

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

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

Khalafi Sara, Bagheri Alireza, Riahi Kashani M. M., (2014), "Finding The Biggest Monochromatic Polygon", INTERNATIONAL JOURNAL OF Scientific & Technology Research Volume 3, Issue 3.

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