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.
Recommendations
Cites work
- scientific article; zbMATH DE number 429516 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 1759203 (Why is no real title available?)
- Codes on Euclidean spheres
- Computing the arrangement of circles on a sphere, with applications in structural biology
- Covering a ball with smaller equal balls in R^n
- Covering point sets with two disjoint disks or squares
- Covering points with a polygon
- Covering spheres with spheres
- Introduction to algorithms
- On a cone covering problem
- On the complexity of four polyhedral set containment problems
Cited in
(1)
This page was built for publication: Spherical coverage verification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q440948)
