Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-013 | 22nd December 2004 00:00

Theory and Application of Width Bounded Geometric Separator


Authors: Bin Fu
Publication: 25th January 2005 08:00
Downloads: 3055


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

ISSN 1433-8092 | Imprint