Show simple item record

dc.creatorPetković, MD
dc.creatorPokrajac, D
dc.creatorLatecki, LJ
dc.date.accessioned2021-02-04T21:11:27Z
dc.date.available2021-02-04T21:11:27Z
dc.date.issued2012-06-01
dc.identifier.issn0096-3003
dc.identifier.issn1873-5649
dc.identifier.doihttp://dx.doi.org/10.34944/dspace/5983
dc.identifier.other935PK (isidoc)
dc.identifier.urihttp://hdl.handle.net/20.500.12613/6001
dc.description.abstractWe 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. © 2012 Elsevier Inc. All rights reserved.
dc.format.extent9699-9715
dc.language.isoen
dc.relation.haspartApplied Mathematics and Computation
dc.relation.isreferencedbyElsevier BV
dc.subjectGeometrical algorithms
dc.subjectQuadratic programming
dc.subjectHypersphere
dc.subjectCoverage
dc.subjectHypercaps
dc.titleSpherical coverage verification
dc.typeArticle
dc.type.genreJournal Article
dc.relation.doi10.1016/j.amc.2012.03.014
dc.ada.noteFor Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.edu
dc.date.updated2021-02-04T21:11:24Z
refterms.dateFOA2021-02-04T21:11:27Z


Files in this item

Thumbnail
Name:
1109.2361v1.pdf
Size:
1.205Mb
Format:
PDF

This item appears in the following Collection(s)

Show simple item record