Theory and application of width bounded geometric separators (Q632801)

In this paper the notion of width bounded geometric separator is presented and techniques for proving the existence of a width bounded separator in any fixed \(d\)-dimensional Euclidean space are developed. The brute-force algorithm of a width bounded geometric separator computation is given. Separators are applied in obtaining \(2^{O(\sqrt n)}\) time exact algorithms for a class of NP-complete geometric problems whose previous algorithms take \(n^{O(\sqrt 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 \(Q_{1}\) (on the left side of the region), \(S\) (inside the region), and \(Q_{2}\) (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 \(Q_{1}, S\) and \(Q_{2}\) such that \(|Q_{1}|,|Q_{2}| \leqslant (2/3)n\), and \(|S| \leqslant 1.2126a \sqrt n\). The width bounded separator in \(d\)-dimensional Euclidean space with fixed \(d\) is controlled by two parallel hyper-planes, and is used to design \(2^{O(n^{1-\frac 1d})}\)-time algorithms for the \(d\)-dimensional disk covering problem and the above other problems in the \(d\)-dimensional disk graphs. The results of this paper are a generalization and improvement of the results obtained by \textit{B. Fu} and \textit{W. Wang} [SIAM J. Comput. 37, No.~4, 1014--1029 (2007; Zbl 1167.68463)].