Abstract: Marko Petković

Algorithms for the spherical coverage verification

           We considered the problem of covering hypersphere by set of spherical hypercaps. Such problem has numerous practical applications such as design of the satellite systems, error correcting codes and $k$-nearest neighbor problem. Two algorithms are proposed. First algorithm is recursive and reduces the problem on the several lower dimension subproblems. It has the worst case exponential complexity, but it is applicable for practical problems. Second algorithm is based on the quadratic programming. Although it has polynomial time complexity, it is unstable and produce false positives. Both algorithms are tested on a large number of generated constellation, which shows the correctness and practical applicability of these algorithms.

 

Joint work with: D. Pokrajac, L.J. Latecki, J. Milutinović