__
TR05-013 | 22nd December 2004 00:00
__

#### Theory and Application of Width Bounded Geometric Separator

TR05-013
Authors:

Bin Fu
Publication: 25th January 2005 08:00

Downloads: 1463

Keywords:

**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}$.