Paper Info

Title | ||
---|---|---|

Polynomial-time approximation schemes for piercing and covering with applications in wireless networks |

Abstract | ||
---|---|---|

Let D be a set of disks of arbitrary radii in the plane, and let P be a set of points. We study the following three problems: (i) Assuming P contains the set of center points of disks in D, find a minimum-cardinality subset P^* of P (if exists), such that each disk in D is pierced by at least h points of P^*, where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming P is such that for each D@?D there exists a point in P whose distance from D's center is at most @ar(D), where r(D) is D's radius and 0= |

Year | DOI | Venue |
---|---|---|

2008 | 10.1016/j.comgeo.2007.01.001 | Comput. Geom. |

Keywords | Field | DocType |

geometric optimization,minimum-cardinality subset,wireless network,approximation algorithms,discrete piercing,covering,polynomial-time approximation scheme,wireless networks,center point,h point,arbitrary radius,problem minimum h-piercing,polynomial time approximation scheme | Wireless network,Discrete mathematics,Approximation algorithm,Combinatorics,Existential quantification,Radius,Time complexity,Mathematics | Journal |

Volume | Issue | ISSN |

39 | 3 | Computational Geometry: Theory and Applications |

Citations | PageRank | References |

7 | 0.49 | 16 |

Authors | ||

3 |

Authors (3 rows)

Cited by (7 rows)

References (16 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Paz Carmi | 1 | 321 | 43.14 |

Matthew J. Katz | 2 | 225 | 19.92 |

Nissan Lev-Tov | 3 | 137 | 7.91 |