An improved parameterized algorithm for hyperplane-cover problem
Academic Article
Overview
Additional Document Info
View All
Overview
abstract
Hyperplane-cover problem is a fundamental NP-hard problem in computational geometry, which has many applications in practice. For the computational hardness of the NP-hard problems, some traditional approaches have been proposed for solving these NP-hard problems. But each of them has its own limitations, and none of them can satisfy all the application requirements in practice. Recently, a new approach dealing with NP-hard problems, called parameterized computation, has been developed, which has been effectively used in solving many hard problems. In this paper, based on the further structure analysis of the line-cover problem(a special case of hyperplane-cover problem), a deterministic parameterized algorithm with running time O(k3(0.736k)k+n log k) is proposed for the problem using depth-bounded search tree method, which significantly improves the previous best result O((k/2.2)2k+n log k). The improvement is due to taking the advantages of the relationship between points and lines, and due to the precise algorithm's running time analysis. Moreover, based on the generalization of the algorithm solving the line-cover problem in higher space, a deterministic parameterized algorithm for the hyperplane-cover problem with running time O(dkd+1(dk)!/((d!)kk!)+nd+1) is given, which greatly improves the previous best result O(kd(k+1)+nd+1). In particular, the algorithms proposed can be used to solve many other covering problems, such as covering points with spheres, covering points with polynomials, covering by sets with intersection at most d, etc.
