Conference Paper: Minimizing the number of separating circles for two sets of points in the plane

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleMinimizing the number of separating circles for two sets of points in the plane
AuthorsWang, J1
Sun, F3
Wang, W3
Miao, C4
Zhang, C2
KeywordsApproximation Algorithm
Bichromatic Points
Delaunay Triangulation
Separating Circle
Separation
Issue Date2011
CitationProceedings - 2011 8Th International Symposium On Voronoi Diagrams In Science And Engineering, Isvd 2011, 2011, p. 98-104 [How to Cite?]
DOI: http://dx.doi.org/10.1109/ISVD.2011.21
AbstractGiven two sets of points ℝ and double-struck B in the plane, we address the problem of finding a set of circles ℂ = {c i, i = 1, 2,...,k}, satisfying the condition that every point in ℝ is covered by at least one circle ℂ and each point in double-struck B is not covered by any circle ℂ. We conjecture that to find such a set with the smallest k is NP-complete. 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. © 2011 IEEE.
DOIhttp://dx.doi.org/10.1109/ISVD.2011.21
ReferencesReferences in Scopus
DC Field
Value
dc.contributor.authorWang, J
dc.contributor.authorSun, F
dc.contributor.authorWang, W
dc.contributor.authorMiao, C
dc.contributor.authorZhang, C
dc.date.accessioned2012-06-26T06:32:24Z
dc.date.available2012-06-26T06:32:24Z
dc.date.issued2011
dc.description.abstractGiven two sets of points ℝ and double-struck B in the plane, we address the problem of finding a set of circles ℂ = {c i, i = 1, 2,...,k}, satisfying the condition that every point in ℝ is covered by at least one circle ℂ and each point in double-struck B is not covered by any circle ℂ. We conjecture that to find such a set with the smallest k is NP-complete. 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. © 2011 IEEE.
dc.description.natureLink_to_subscribed_fulltext
dc.identifier.citationProceedings - 2011 8Th International Symposium On Voronoi Diagrams In Science And Engineering, Isvd 2011, 2011, p. 98-104 [How to Cite?]
DOI: http://dx.doi.org/10.1109/ISVD.2011.21
dc.identifier.doihttp://dx.doi.org/10.1109/ISVD.2011.21
dc.identifier.epage104
dc.identifier.scopuseid_2-s2.0-80052629298
dc.identifier.spage98
dc.identifier.urihttp://hdl.handle.net/10722/152009
dc.languageeng
dc.relation.ispartofProceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011
dc.relation.referencesReferences in Scopus
dc.subjectApproximation Algorithm
dc.subjectBichromatic Points
dc.subjectDelaunay Triangulation
dc.subjectSeparating Circle
dc.subjectSeparation
dc.titleMinimizing the number of separating circles for two sets of points in the plane
dc.typeConference_Paper
Author Affiliations
  1. Shandong Econimical University
  2. Shandong University
  3. The University of Hong Kong
  4. Nanyang Technological University School of Computer Engineering