Genre
Journal ArticleDate
2012-06-01Author
Petković, MDPokrajac, D
Latecki, LJ
Permanent link to this record
http://hdl.handle.net/20.500.12613/6001
Metadata
Show full item recordDOI
10.1016/j.amc.2012.03.014Abstract
We consider the problem of covering hypersphere by a set of spherical hypercaps. This sort of problem has numerous practical applications such as error correcting codes and reverse k-nearest neighbor problem. Using the reduction of non-degenerated concave quadratic programming (QP) problem, we demonstrate that spherical coverage verification is NP hard. We propose a recursive algorithm based on reducing the problem to several lower dimension subproblems. We test the performance of the proposed algorithm on a number of generated constellations. We demonstrate that the proposed algorithm, in spite of its exponential worst-case complexity, is applicable in practice. In contrast, our results indicate that spherical coverage verification using QP solvers that utilize heuristics, due to numerical instability, may produce false positives. © 2012 Elsevier Inc. All rights reserved.Citation to related work
Elsevier BVHas part
Applied Mathematics and ComputationADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.eduae974a485f413a2113503eed53cd6c53
http://dx.doi.org/10.34944/dspace/5983