File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleMinimizing the number of separating circles for two sets of points in the plane
Authors
Wang, JSun, FWang, WMiao, CZhang, C
KeywordsApproximation Algorithm
Bichromatic Points
Delaunay Triangulation
Separating Circle
Separation
Issue Date2011
Citation
Proceedings - 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.
Persistent Identifierhttp://hdl.handle.net/10722/152009
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorWang, Jen_US
dc.contributor.authorSun, Fen_US
dc.contributor.authorWang, Wen_US
dc.contributor.authorMiao, Cen_US
dc.contributor.authorZhang, Cen_US
dc.date.accessioned2012-06-26T06:32:24Z-
dc.date.available2012-06-26T06:32:24Z-
dc.date.issued2011en_US
dc.identifier.citationProceedings - 2011 8Th International Symposium On Voronoi Diagrams In Science And Engineering, Isvd 2011, 2011, p. 98-104en_US
dc.identifier.urihttp://hdl.handle.net/10722/152009-
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.en_US
dc.languageengen_US
dc.relation.ispartofProceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011en_US
dc.subjectApproximation Algorithmen_US
dc.subjectBichromatic Pointsen_US
dc.subjectDelaunay Triangulationen_US
dc.subjectSeparating Circleen_US
dc.subjectSeparationen_US
dc.titleMinimizing the number of separating circles for two sets of points in the planeen_US
dc.typeConference_Paperen_US
dc.identifier.emailWang, W:wenping@cs.hku.hken_US
dc.identifier.authorityWang, W=rp00186en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1109/ISVD.2011.21en_US
dc.identifier.scopuseid_2-s2.0-80052629298en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-80052629298&selection=ref&src=s&origin=recordpageen_US
dc.identifier.spage98en_US
dc.identifier.epage104en_US
dc.identifier.scopusauthoridWang, J=8384548600en_US
dc.identifier.scopusauthoridSun, F=35068615100en_US
dc.identifier.scopusauthoridWang, W=35147101600en_US
dc.identifier.scopusauthoridMiao, C=8850060600en_US
dc.identifier.scopusauthoridZhang, C=35197623400en_US

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats