Theory and application of width bounded geometric separators

摘要

We introduce the notion of the width bounded geometric separator and develop the techniques for the existence of the width bounded separator in any fixed d-dimensional Euclidean space. The separator is applied in obtaining 2O(n) time exact algorithms for a class of NP-complete geometric problems, whose previous algorithms take nO(n) time. One of those problems is the well-known disk covering problem, which seeks to determine the minimal number of fixed size disks to cover n points on a plane. They also include some NP-hard problems on disk graphs such as the maximum independent set problem, the vertex cover problem, and the minimum dominating set problem. For a constant a>0 and a set of points Q on the plane, an a-wide separator is the region between two parallel lines of distance a that partitions Q into Q1 (on the left side of the region), S (inside the region), and Q2 (on the right side of the region). If the distance is at least one between every two points in the set Q with n points, there is an a-wide separator that partitions Q into Q1, S and Q2 such that |Q1|,|Q2|⩽(2/3)n, and |S|⩽1.2126an. Our width bounded separator in d-dimensional Euclidean space with fixed d is controlled by two parallel hyper-planes, and is used to design 2O(n1−1d)-time algorithms for the d-dimensional disk covering problem and the above other problems in the d-dimensional disk graphs.