Advertisement
Published in:
2006 | OriginalPaper | Chapter
Theory and Application of Width Bounded Geometric Separator
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We introduce the notion of the width bounded geometric separator and develop the techniques for the existence of the width bounded separator in any
d
-dimensional Euclidean space. The separator is 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[2][5][1]. 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[10]. 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.