A parameterized algorithm for the hyperplane-cover problem Academic Article uri icon

abstract

  • We consider the problem of covering a given set of points in the Euclidean space m by a small number k of hyperplanes of dimensions bounded by d, where dm. We present a very simple parameterized algorithm for the problem, and give thorough mathematical analysis to prove the correctness and derive the complexity of the algorithm. When the algorithm is applied on the standard hyperplane-cover problem in d, it runs in time O*(k(d-1)k/1.3k), improving the previous best algorithm of running time O*(kdk+d) for the problem. When the algorithm is applied on the line-cover problem in 2, it runs in time O*(kk1.35k), improving the previous best algorithm of running time O*(k2k4.84k) for the problem. 2010 Elsevier B.V. All rights reserved.

published proceedings

  • Theoretical Computer Science

author list (cited authors)

  • Wang, J., Li, W., & Chen, J.

citation count

  • 9

complete list of authors

  • Wang, Jianxin||Li, Wenjun||Chen, Jianer

publication date

  • October 2010