Finding Two Maximum Separating Circles
سال انتشار: 1393
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 853
فایل این مقاله در 7 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_ACSIJ-3-4_011
تاریخ نمایه سازی: 5 شهریور 1393
چکیده مقاله:
In this paper, for the first time an algorithm is presented for separating the points by two circles. Separating the points by circles is one of the problems in computational geometry beingapplied in different fields of science, some of which are: facility location, image processing and clustering. Our algorithm findsthe locations of two smallest circles in the plane such that these two circles cover as many as points of Q while avoid the pointsof P. The running time of the algorithm is O(n2), where n is total number of input points. The experimental results show that ouralgorithm succeeds to find near-optimal solutions, with anapproximation factor of 1.32 in average. The proposed algorithm is not optimal, but in some cases it yields optimum solutions
کلیدواژه ها:
نویسندگان
Afsaneh Hellatabadi Farahani
Faculty of Engineering, Tehran North Branch, Islamic Azad University,Tehran, Iran
Alireza Bagheri
Department of Computer Engineering and Information Technology, Amirkabir University, Tehran, Iran