Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Algorithms and Complexity Group Friday, November 23, 2012: Algorithms for Geometric Covering and Piercing Problems
2 views
Skip to first unread message
wlr...@uwaterloo.ca
Oct 22, 2012, 2:01:27 PM10/22/12
to
A new Algorithms and Complexity Group event has been scheduled:
Algorithms for Geometric Covering and Piercing Problems
This thesis involves the study of a range of geometric covering and piercing problems, where the unifying thread is approximation using disks. While some of the problems addressed in this work are solved with polynomial time algorithms, many problems are shown to be at least NP-hard. For the latter, approximation algorithms are the best that we can do in polynomial time assuming that P!=NP.
One of the best known problems involving unit disks is the Discrete Unit Disk Cover (DUDC) problem, in which the input consists of a set of points P and a set of unit disks in the plane D, and the objective is to compute a subset of the disks of minimum cardinality which covers all of the points. Another perspective on the problem is to consider the centre points of the disks Q as an approximating set of points for P. An optimal solution to DUDC provides a minimal cardinality subset Q* of Q so that each point in P is within unit distance of a point in Q*. In order to approximate the general DUDC problem, we also examine several restricted variants.
In the Line-Separable Discrete Unit Disk Cover (LSDUDC) problem, P and Q may be separated by a line in the plane. LSDUDC may be solved exactly in O(mn + n log n) time using a greedy algorithm. We augment this result by describing a 2-approximate solution for the Assisted LSDUDC problem, where Q may lie on either side of the separating line, yet all points in P may be covered by disks centred on the opposite side of the line from P.
Next, we describe the Within-Strip Discrete Unit Disk Cover (WSDUDC) problem, where P and Q are confined to a strip of the plane of height h. We show that this problem is NP-complete, and we provide a range of approximation algorithms for the problem with trade-offs between approximation factor and running time.
We outline approximation algorithms for the general DUDC problem which make use of the algorithms for LSDUDC and WSDUDC. These results provide the fastest known approximation algorithms for DUDC. As with the WSDUDC results, we present a set of algorithms in which better approximation factors may be had at the expense of greater running time, ranging from a 15-approximate algorithm which runs in O(m^6n) time to a 18-approximate algorithm which runs in O(n log n + mn) time.
The next problems that we study are Hausdorff Core problems. These problems accept an input polygon P, and we seek a convex polygon Q which is fully contained in P and minimizes the Hausdorff distance between P and Q. Interestingly, we show that this problem may be reduced to that of computing the minimum radius of disk, call it r, so that a convex polygon Q contained in P intersects all disks of radius r centred on the vertices of P. We begin by describing a polynomial time algorithm for the simple case where P has only a single reflex vertex. On general polygons, we provide an FPTAS which performs a parametric search on the possible values of r. The solution to the decision version of the problem, i.e. determining whether there exists a Hausdorff Core for P given r, requires some novel insights.
Finally, we study Generalized Minimum Spanning Tree (GMST) problems, where the input consists of imprecise vertices, and the objective is to select a single vertex from each imprecise vertex in order to optimize the value of the MST over the points. In keeping with one of the themes of the thesis, we begin by using disks as the imprecise vertices. We show that the minimization and maximization versions of this problem are NP-hard, and we describe some parameterized and approximation algorithms. Finally, we look at the case where the imprecise vertices consist of just two vertices each, and we show that the minimization version of the problem (which we call 2-GMST) remains NP-hard, even in the plane. We also provide algorithms to solve the problem exactly given some simplifying assumptions, such as if the combinatorial structure of the optimal solution is known.
Date: Friday, November 23, 2012
Time: 10:30
Please look on WebCalendar to view this appointment.
http://www.cs.uwaterloo.ca/odyssey/event/1611
Algorithms for Geometric Covering and Piercing Problems
This thesis involves the study of a range of geometric covering and piercing problems, where the unifying thread is approximation using disks. While some of the problems addressed in this work are solved with polynomial time algorithms, many problems are shown to be at least NP-hard. For the latter, approximation algorithms are the best that we can do in polynomial time assuming that P!=NP.
One of the best known problems involving unit disks is the Discrete Unit Disk Cover (DUDC) problem, in which the input consists of a set of points P and a set of unit disks in the plane D, and the objective is to compute a subset of the disks of minimum cardinality which covers all of the points. Another perspective on the problem is to consider the centre points of the disks Q as an approximating set of points for P. An optimal solution to DUDC provides a minimal cardinality subset Q* of Q so that each point in P is within unit distance of a point in Q*. In order to approximate the general DUDC problem, we also examine several restricted variants.
In the Line-Separable Discrete Unit Disk Cover (LSDUDC) problem, P and Q may be separated by a line in the plane. LSDUDC may be solved exactly in O(mn + n log n) time using a greedy algorithm. We augment this result by describing a 2-approximate solution for the Assisted LSDUDC problem, where Q may lie on either side of the separating line, yet all points in P may be covered by disks centred on the opposite side of the line from P.
Next, we describe the Within-Strip Discrete Unit Disk Cover (WSDUDC) problem, where P and Q are confined to a strip of the plane of height h. We show that this problem is NP-complete, and we provide a range of approximation algorithms for the problem with trade-offs between approximation factor and running time.
We outline approximation algorithms for the general DUDC problem which make use of the algorithms for LSDUDC and WSDUDC. These results provide the fastest known approximation algorithms for DUDC. As with the WSDUDC results, we present a set of algorithms in which better approximation factors may be had at the expense of greater running time, ranging from a 15-approximate algorithm which runs in O(m^6n) time to a 18-approximate algorithm which runs in O(n log n + mn) time.
The next problems that we study are Hausdorff Core problems. These problems accept an input polygon P, and we seek a convex polygon Q which is fully contained in P and minimizes the Hausdorff distance between P and Q. Interestingly, we show that this problem may be reduced to that of computing the minimum radius of disk, call it r, so that a convex polygon Q contained in P intersects all disks of radius r centred on the vertices of P. We begin by describing a polynomial time algorithm for the simple case where P has only a single reflex vertex. On general polygons, we provide an FPTAS which performs a parametric search on the possible values of r. The solution to the decision version of the problem, i.e. determining whether there exists a Hausdorff Core for P given r, requires some novel insights.
Finally, we study Generalized Minimum Spanning Tree (GMST) problems, where the input consists of imprecise vertices, and the objective is to select a single vertex from each imprecise vertex in order to optimize the value of the MST over the points. In keeping with one of the themes of the thesis, we begin by using disks as the imprecise vertices. We show that the minimization and maximization versions of this problem are NP-hard, and we describe some parameterized and approximation algorithms. Finally, we look at the case where the imprecise vertices consist of just two vertices each, and we show that the minimization version of the problem (which we call 2-GMST) remains NP-hard, even in the plane. We also provide algorithms to solve the problem exactly given some simplifying assumptions, such as if the combinatorial structure of the optimal solution is known.
Date: Friday, November 23, 2012
Time: 10:30
Please look on WebCalendar to view this appointment.
http://www.cs.uwaterloo.ca/odyssey/event/1611
0 new messages