This item is non-discoverable
Loading...
Non-discoverable
Spherical coverage verification
Petković, MD Pokrajac, D Latecki, LJ
Petković, MD
Pokrajac, D
Latecki, LJ
An error occurred retrieving the object's statistics
Citations
Altmetric:
Genre
Journal Article
Date
2012-06-01
Advisor
Committee member
Group
Department
Permanent link to this record
Collections
Research Projects
Organizational Units
Journal Issue
DOI
10.1016/j.amc.2012.03.014
Abstract
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.
Description
Citation
Citation to related work
Elsevier BV
Has part
Applied Mathematics and Computation
ADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.edu