Spherical coverage verification

Details Spherical coverage verification Spherical coverage verification

2011-09-11

arxiv.org/abs/1109.2361v1

Computer Science

Computational Geometry

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Spherical coverage verification does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spherical coverage verification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spherical coverage verification will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-59395