File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Minimizing the number of separating circles for two sets of points in the plane
  • 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 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.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
 
<?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>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1109/ISVD.2011.21</identifier.doi>
<identifier.scopus>eid_2-s2.0-80052629298</identifier.scopus>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-80052629298&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.spage>98</identifier.spage>
<identifier.epage>104</identifier.epage>
</item>
Author Affiliations
  1. Shandong Econimical University
  2. Shandong University
  3. The University of Hong Kong
  4. Nanyang Technological University School of Computer Engineering