Spherical coverage verification

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.

• Publication year

  2011

• Venue

  Applied Mathematics and Computation

• Publication date

  2011-09-11

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1016/j.amc.2012.03.014arXiv 1109.2361
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the complexity of four polyhedral set containment problems

  2018cited by this paper
• On a cone covering problem

  2011cited by this paper
• Optimization Theory and Methods: Nonlinear Programming

  2010cited by this paper
• Optimal Quadratic Programming Algorithms: With Applications to Variational Inequalities

  2009cited by this paper
• Computing the arrangement of circles on a sphere, with applications in structural biology

  2009cited by this paper
• Incremental Connectivity-Based Outlier Factor Algorithm

  2008cited by this paper
• Covering point sets with two disjoint disks or squares

  2008cited by this paper
• Incremental Local Outlier Detection for Data Streams

  2007cited by this paper
• Efficient reverse k-nearest neighbor search in arbitrary metric spaces

  2006cited by this paper
• Covering Spheres with Spheres

  2006cited by this paper
• Covering points with a polygon

  2005cited by this paper
• Covering a Ball with Smaller Equal Balls in ℝn

  2005cited by this paper
• Reverse kNN Search in Arbitrary Dimensionality

  2004cited by this paper
• Mining distance-based outliers in near linear time with randomization and a simple pruning rule

  2003cited by this paper
• High dimensional reverse nearest neighbor queries

  2003cited by this paper
• Data Mining - Concepts and Techniques

  2002cited by this paper
• Introduction to Algorithms, 2nd edition.

  2001cited by this paper
• The inverse nearest neighbor problem with astrophysical applications

  2001cited by this paper
• Codes on euclidean spheres

  2001cited by this paper
• Reverse Nearest Neighbor Queries for Dynamic Databases

  2000cited by this paper
• Sphere packings, I

  1998cited by this paper
• AMPL: A Modeling Language for Mathematical Programming

  1993cited by this paper
• Nonlinear optimization: complexity issues

  1991cited by this paper
• Introduction to Algorithms

  1991cited by this paper
• Quadratic Programming is in NP

  1990cited by this paper
• Sphere Packings, Lattices and Groups

  1990cited by this paper
• Thomson’s problem

  1986cited by this paper
• The polynomial solvability of convex quadratic programming

  1980cited by this paper
• The Theory of Error-Correcting Codes

  1977cited by this paper
• The theory of error-correcting codes (north-holland

  1977cited by this paper
• Computationally Related Problems

  1974cited by this paper
• Real Analysis

  1972cited by this paper
• Handbook of Mathematical Functions with Formulas, Graphs,

  1971cited by this paper
• "PROOF"

  1934cited by this paper
• An Introduction to the Geometry of N Dimensions

  year unknowncited by this paper
• A New Development of the Theory of the Hypergeometric Functions

  year unknowncited by this paper

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

  2023influential citation
• Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere

  2019cites this paper
• THE UNIVERSITY OF CHICAGO SPHERICAL DISCREPANCY A DISSERTATION SUBMITTED TO THE FACULTY OF THE DIVISION OF THE PHYSICAL SCIENCES IN CANDIDACY FOR THE DEGREE OF MASTER OF SCIENCE DEPARTMENT OF COMPUTER SCIENCE BY CHRIS JONES

  2019cites this paper
• Rate-Adaptive Feedback With Bayesian Compressive Sensing in Multiuser MIMO Beamforming Systems

  2016cites this paper
• Incremental multiple instance outlier detection

  2015cites this paper
• THE FEKETE PROBLEM AND CONSTRUCTION OF THE SPHERICAL COVERAGE BY CONES

  2013cites this paper