Spherical coverage verification

DOI10.1016/J.AMC.2012.03.014zbMATH Open1245.90083arXiv1109.2361OpenAlexW2068050483MaRDI QIDQ440948FDOQ440948

Authors: Marko D. Petković, Dragoljub Pokrajac, Longin Jan Latecki 

Publication date: 19 August 2012

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1109.2361

Recommendations

• Random sequential covering of a sphere with identical spherical caps
• Covering a simplex by spheres: complexity and algorithms
• Random sequential covering of a sphere with identical spherical caps
• Optimal coverage of convex regions
• scientific article; zbMATH DE number 559076

zbMATH Keywords

quadratic programmingcoveragehyperspheregeometrical algorithmshypercaps

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Introduction to algorithms
• Title not available (Why is that?)
• Covering point sets with two disjoint disks or squares
• Title not available (Why is that?)
• On a cone covering problem
• Covering a ball with smaller equal balls in \(\mathbb R^n\)
• Covering points with a polygon
• Covering spheres with spheres
• Codes on Euclidean spheres
• On the complexity of four polyhedral set containment problems
• Title not available (Why is that?)
• Computing the arrangement of circles on a sphere, with applications in structural biology

Cited In (1)

• Approximating Tensor Norms via Sphere Covering: Bridging the Gap between Primal and Dual

Uses Software

• AMPL

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)