Is a Finite Intersection of Balls Covered by a Finite Union of Balls in Euclidean Spaces?
- PDF / 724,675 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 55 Downloads / 206 Views
Is a Finite Intersection of Balls Covered by a Finite Union of Balls in Euclidean Spaces? Vincent Runge1 Received: 4 June 2019 / Accepted: 29 September 2020 / Published online: 24 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Considering a finite intersection of balls and a finite union of other balls in an Euclidean space, we propose an exact method to test whether the intersection is covered by the union. We reformulate this problem into quadratic programming problems. For each problem, we study the intersection between a sphere and a Voronoi-like polyhedron. That way, we get information about a possible overlap between the frontier of the union and the intersection of balls. If the polyhedra are non-degenerate, the initial nonconvex geometric problem, which is NP-hard in general, is tractable in polynomial time by convex optimization tools and vertex enumeration. Under some mild conditions, the vertex enumeration can be skipped. Simulations highlight the accuracy and efficiency of our approach compared with competing algorithms in Python for nonconvex quadratically constrained quadratic programming. This work is motivated by an application in statistics to the problem of multidimensional changepoint detection using pruned dynamic programming algorithms. Keywords Ball covering problem · Nonconvex quadratically constrained quadratic programming · Computational geometry · Voronoi-like polyhedron · Vertex enumeration · Polynomial time complexity Mathematics Subject Classification 52C17 · 90C26 · 68U05 · 62L10
1 Introduction Geometric problems for balls often separately address the intersection and the union problems. Without optimization tools, the detection of a nonempty intersection
Communicated by Juan-Enrique Martinez Legaz.
B 1
Vincent Runge [email protected] Université Paris-Saclay, CNRS, Univ Evry, Laboratoire de Mathématiques et Modélisation d’Evry, 91037 Evry-Courcouronnes, France
123
432
Journal of Optimization Theory and Applications (2020) 187:431–447
between balls is difficult to solve. Helly-type theorems can be adapted to balls [1,2], but no efficient algorithm arises from this approach. The union of balls is a problem linked in the literature to molecular structures, where the volume and the surface area of molecules in 3D are important properties. Powerful algorithms based on Voronoi diagrams have been recently developed [3,4]. Even if the number of balls is small, that is more than two, the exact computation of simple geometric properties, as volume, is a challenging question [5]. One of the first problems to associate union and intersection is the historical disk covering problem, which consists in finding the minimum number of identical disks (with a given radius) needed to cover the unit disk [6]. This problem is still open and remains mainly unsolved, although research on this subject is active [7,8] as it has practical applications, for example in optical interferometry [9]. Our problem also involves covers but is different in sever
Data Loading...
