Abstract:
We introduce the notion of width bounded geometric separator, develop the techniques for its existence as well as algorithm, and apply it to obtain a $2^{O(\sqrt{n})}$ time exact algorithm for the disk covering problem, which seeks to determine the minimal number of fixed size disks to cover $n$ points on plane, and was proven to be NP-complete. Applying our separator to a class of NP-hard problems on disk graphs, we also greatly improve the exact algorithm for maximum independent set problem on disk graph to $2^{O(\sqrt{n})}$ from $n^{O(\sqrt{n})}$. 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$ (in the left side of the region), $S$ (inside the region), and $Q_2$ (in the right side of the region). If the distance is at least one between every two points in the set $Q$ with $n$ points, called $1$-separated set, there is an $a$-wide separator that partitions $Q$ into $Q_1,S$ and $Q_2$ such that $|Q_1|,|Q_2|\le (2/3)n$, and $|S|\le 1.2126a\sqrt{n}$.