...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Applied mathematics and computation >Spherical coverage verification
【24h】

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.
机译：我们考虑用一组球面超上限覆盖超球面的问题。这类问题有许多实际应用，例如纠错码和反向k最近邻问题。使用非退化凹二次规划（QP）问题的减少，我们证明球面覆盖验证是NP困难的。我们提出了一种基于递归算法，将问题减少到几个较低维度的子问题。我们在许多生成的星座图上测试了所提出算法的性能。我们证明了所提出的算法尽管具有指数级的最坏情况复杂度，但仍可在实践中应用。相反，我们的结果表明，由于数值不稳定，使用利用启发式方法的QP求解器进行的球形覆盖范围验证可能会产生假阳性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号