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

Title | Minimizing the number of separating circles for two sets of points in the plane |
---|---|

Authors | Wang, J1 Sun, F3 Wang, W3 Miao, C4 Zhang, C2 |

Keywords | Approximation Algorithm Bichromatic Points Delaunay Triangulation Separating Circle Separation |

Issue Date | 2011 |

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 |

Abstract | 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. |

DOI | http://dx.doi.org/10.1109/ISVD.2011.21 |

References | References in Scopus |

DC Field | Value |
---|---|

dc.contributor.author | Wang, J |

dc.contributor.author | Sun, F |

dc.contributor.author | Wang, W |

dc.contributor.author | Miao, C |

dc.contributor.author | Zhang, C |

dc.date.accessioned | 2012-06-26T06:32:24Z |

dc.date.available | 2012-06-26T06:32:24Z |

dc.date.issued | 2011 |

dc.description.abstract | 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. |

dc.description.nature | link_to_subscribed_fulltext |

dc.identifier.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 |

dc.identifier.doi | http://dx.doi.org/10.1109/ISVD.2011.21 |

dc.identifier.epage | 104 |

dc.identifier.scopus | eid_2-s2.0-80052629298 |

dc.identifier.spage | 98 |

dc.identifier.uri | http://hdl.handle.net/10722/152009 |

dc.language | eng |

dc.relation.ispartof | Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011 |

dc.relation.references | References in Scopus |

dc.subject | Approximation Algorithm |

dc.subject | Bichromatic Points |

dc.subject | Delaunay Triangulation |

dc.subject | Separating Circle |

dc.subject | Separation |

dc.title | Minimizing the number of separating circles for two sets of points in the plane |

dc.type | Conference_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 ℝ 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.</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&selection=ref&src=s&origin=recordpage</relation.references> <identifier.spage>98</identifier.spage> <identifier.epage>104</identifier.epage> </item>

Author Affiliations

- Shandong Econimical University
- Shandong University
- The University of Hong Kong
- Nanyang Technological University School of Computer Engineering