Permanent link to this recordhttp://hdl.handle.net/20.500.12613/6001
MetadataShow full item record
AbstractWe 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 workElsevier BV
Has partApplied Mathematics and Computation
ADA complianceFor Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact firstname.lastname@example.org