BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We consider the problem of covering the boundary of a simple polygon on n vertices using the minimum number of geodesic unit disks. We present an O(n \log^2 n+k) time 2-approximation algorithm for finding the centers of the disks, with k denoting the number centers found by the algorithm.
Given a polygon P, for two points s and t contained in the polygon, their \emph{geodesic distance} is the length of the shortest st-path within P. A \emph{geodesic disk} of radius r centered at a point v∈P is the set of points in P whose geodesic distance to v is at most r. We present a polynomial time 2-approximation algorithm for finding a densest geodesic unit disk packing in P. Allowing arbitrary radii but constraining the number of disks to be k, we present a 4-approximation algorithm for finding a packing in P with k geodesic disks whose minimum radius is maximized. We then turn our focus on \emph{coverings} of P and present a 2-approximation algorithm for covering P with k geodesic disks whose maximal radius is minimized. Furthermore, we show that all these problems are NP-hard in polygons with holes. Lastly, we present a polynomial time exact algorithm which covers a polygon with two geodesic disks of minimum maximal radius.
We consider the situation where one is given a set S of points in the plane and a collection D of unit disks embedded in the plane. We show that finding a minimum cardinality subset of D such that any path between any two points in S is intersected by at least one disk is NP-complete. This settles an open problem raised by Matt Gibson et al[1]. Using a similar reduction, we show that finding a minimum cardinality subset D' of D such that R^2 - (D - D') consists of a single connected region is also NP-complete. Lastly, we show that the Multiterminal Cut Problem remains NP-complete when restricted to unit disk graphs.
In this paper, we focus on families of bipartitions, i.e. set partitions consisting of at most two components. We say that a family of bipartitions is a separating family for a set S if every two elements in S can be separated by some bipartition. Furthermore, we call a separating family minimal if no proper subfamily is a separating family. We characterize the set of all minimal separating families of maximum size for arbitrary set S as the set of all spanning trees on S and enumerate minimal separating families of maximum size. Furthermore, we enumerate separating families of arbitrary size, which need not be minimal.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.