Title :
Minimizing the Number of Separating Circles for Two Sets of Points in the Plane
Author :
Wang, Jiaye ; Sun, Feng ; Wang, Wenping ; Miao, Chunyan ; Zhang, Caiming
Author_Institution :
Dept. of Comput. Sci., Shandong Econimical Univ., Jinan, China
Abstract :
Given two sets of points ℝ and B in the plane, we address the problem of finding a set of circles ℂ = {ci, i = 1, 2,... ,k}, satisfying the condition that every point in ℝ is covered by at least one circle in ℂ and each point in B is not covered by any circle in ℂ. We conjecture that to find such a set with the smallest k is NP-hard. In this paper, we present an approximation algorithm for computing the set with minimal number of such circles. The algorithm finds also a lower bound of the smallest k.
Keywords :
approximation theory; computational complexity; geometry; NP hard; approximation algorithm; plane; point sets; separating circles; Approximation algorithms; Approximation methods; Complexity theory; Computer science; Law; Solids; Delaunay triangulation; approximation algorithm; bichromatic points; separating circle; separation;
Conference_Titel :
Voronoi Diagrams in Science and Engineering (ISVD), 2011 Eighth International Symposium on
Conference_Location :
Qingdao
Print_ISBN :
978-1-4577-1026-1
Electronic_ISBN :
978-0-7695-4483-0
DOI :
10.1109/ISVD.2011.21
