• No File Attached

(May Require Subscription)

Supplementary
• Citations:
• Appears in Collections:

Conference Paper: Minimizing the number of separating circles for two sets of points in the plane
• Basic View
• XML View
Title Minimizing the number of separating circles for two sets of points in the plane Wang, J1Sun, F3Wang, W3Miao, C4Zhang, C2 Approximation AlgorithmBichromatic PointsDelaunay TriangulationSeparating CircleSeparation 2011 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 Given 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. http://dx.doi.org/10.1109/ISVD.2011.21 References in Scopus
DC FieldValue
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.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

```<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Wang, J</contributor.author>
<contributor.author>Sun, F</contributor.author>
<contributor.author>Wang, W</contributor.author>
<contributor.author>Miao, C</contributor.author>
<contributor.author>Zhang, C</contributor.author>
<date.accessioned>2012-06-26T06:32:24Z</date.accessioned>
<date.available>2012-06-26T06:32:24Z</date.available>
<date.issued>2011</date.issued>
<identifier.citation>Proceedings - 2011 8Th International Symposium On Voronoi Diagrams In Science And Engineering, Isvd 2011, 2011, p. 98-104</identifier.citation>
<identifier.uri>http://hdl.handle.net/10722/152009</identifier.uri>
<description.abstract>Given two sets of points &#8477; and double-struck B in the plane, we address the problem of finding a set of circles &#8450; = {c i, i = 1, 2,...,k}, satisfying the condition that every point in &#8477; is covered by at least one circle &#8450; and each point in double-struck B is not covered by any circle &#8450;. 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. &#169; 2011 IEEE.</description.abstract>
<language>eng</language>
<relation.ispartof>Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011</relation.ispartof>
<subject>Approximation Algorithm</subject>
<subject>Bichromatic Points</subject>
<subject>Delaunay Triangulation</subject>
<subject>Separating Circle</subject>
<subject>Separation</subject>
<title>Minimizing the number of separating circles for two sets of points in the plane</title>
<type>Conference_Paper</type>