2018/04/18 by Vincent Runge, Runge, Vincent · 1 citation
Decision Sciences · Economics, Econometrics and Finance · Mathematics · #52C17 #62L10 #68U05 #90C26 #Efficiency Analysis Using DEA #FOS: Computer and information sciences #Methodology (stat.ME) #Spatial and Panel Data Analysis #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.1804.06699
openalex publication_date 2018/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Considering a finite intersection of balls and a finite union of other balls\nin an Euclidean space, we propose an exact method to test whether the\nintersection is covered by the union. We reformulate this problem into\nquadratic programming problems. For each problem, we study the intersection\nbetween a sphere and a Voronoi-like polyhedron. That way we get information\nabout a possible overlap between the frontier of the union and the intersection\nof balls. If the polyhedra are non-degenerate, the initial nonconvex geometric\nproblem, which is NP-hard in general, is tractable in polynomial time by convex\noptimization tools and vertex enumeration. Under some mild conditions the\nvertex enumeration can be skipped. Simulations highlight the accuracy and\nefficiency of our approach compared with competing algorithms in Python for\nnonconvex quadratically constrained quadratic programming. This work is\nmotivated by an application in statistics to the problem of multidimensional\nchangepoint detection using pruned dynamic programming algorithms.\n