Is a Finite Intersection of Balls Covered by a Finite Union of Balls in Euclidean Spaces?

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.

1 Introduction

Geometric problems for balls often separately address the intersection and the union problems. Without optimization tools, the detection of a nonempty intersection 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 several important ways. We study the covering of an intersection of balls by other balls, but they are not necessary of the same size. Furthermore, we do not consider the question of the optimal covering, but only the covering test. This problem is part of computational geometry problems and, as far as we know, is original in the literature.

Quadratically constrained quadratic programming (QCQP) problems are a major tool for many practical applications: problems of transmit beamforming in wireless communication [10] or signal processing [11] have stimulated the development of this research area. Asking whether a finite intersection of balls is covered by a finite union of other balls can be reformulated as a collection of nonconvex QCQP problems. However, this approach often fails to return the exact solution and is based on time-consuming iterative algorithms.

In this paper, we transform our problem into quadratic programming problems by introducing hyperplanes “separating” two balls. For each problem, we study the intersection between a sphere and a polyhedron to get information about a possible overlap between the frontier of the union and the intersection of balls. That way, we are able to build an efficient and exact algorithm with polynomial running time in most cases.

This work is motivated by an application to a changepoint detection method in statistics as explained in “Appendix A.”

The outline of this paper is the following. In Sect. 2, we present the problem and introduce the notations. We also give its naive standard resolution by QCQP problems. We end the section with a detailed presentation of our solution. Section 3 focuses on the resolution of a unique QP problem, giving the link between this problem and the initial geometric structure. In “Appendix B,” we propose a similar method adapted to covering tests for a large number of exclusion balls and for sequential tests. With some conditions on the centers and radii of the balls, we are able to ensure that the polyhedron is unbounded and can then skip the maximization problem to only consider the convex quadratic one. We present in Sect. 4 several cases where the only problem to solve is convex. If we have only one exclusion ball, we introduce the so-called concave QCQP problem and highlight simplified results. Finally, in Sect. 5, we compare our approach with recent methods of the Python library ’qcqp’ gathering together the best approaches for solving nonconvex QCQP problem. These simulations highlight the benefit of our method specifically developed for the problem at hand.

2 Preliminaries

2.1 Problem Description

We consider two finite sets of balls in an Euclidean space, $\varLambda = \{B_1,\ldots ,B_p\}$ and $\mathrm V = \{{\mathbf {B}}_1,\ldots ,{\mathbf {B}}_q\}$, with $p,q \in {\mathbb {N}}^*$ and arbitrary centers and radii. We introduce the intersection set ${\mathcal {I}} = \cap _{i=1}^{p}B_i$ and union set ${\mathcal {U}} = \cup _{j=1}^{q}{\mathbf {B}}_j$. Our problem consists in finding an exact and efficient method to decide whether the inclusion ${\mathcal {I}} \subset {\mathcal {U}}$ is true or false. Denoting by ${\mathcal {U}}^{\text {c}}$ the complement of ${\mathcal {U}}$, this problem is equivalent to the study of the emptiness of ${\mathcal {I}}\cap {\mathcal {U}}^{\text {c}}$, which is a challenging question, both theoretically and computationally, due to the non-convexity of the ${\mathbf {B}}_j^{\text {c}}$ sets ($j=1,\ldots ,q$).

With ${\mathbb {R}}^n$ the n-dimensional Euclidean space, $n \ge 2$, we denote by $\langle \cdot ,\cdot \rangle$ the canonic inner product in ${\mathbb {R}}^n$ and by $\Vert \cdot \Vert$ its associated norm. The open balls $B_i$ and closed balls ${\mathbf {B}}_j$ are defined by their centers $c_i,{\mathbf {c}}_j \in {\mathbb {R}}^n$ and radii $R_i,{\mathbf {R}}_j \in {\mathbb {R}}^*_+$, respectively. Thus,

$$\begin{aligned} B_i = \{x \in {\mathbb {R}}^n \,:\, \Vert x-c_{i}\Vert ^2 < R_i^2\} \quad \hbox {and}\quad {\mathbf {B}}_j = \{x \in {\mathbb {R}}^n \,:\, \Vert x-{\mathbf {c}}_{j}\Vert ^2 \le {\mathbf {R}}_j^2\}\,, \end{aligned}$$

where, for example, $\Vert x-c_{i}\Vert ^2 = \sum _{k=1}^{n} (x_k-c_{ik})^2$, with $x = (x_1,\ldots ,x_n)^T \in {\mathbb {R}}^n$. We assume that the centers of balls in $\varLambda \cup V$ are all different (non-concentric) and that for all $(B_a,B_b) \in \varLambda ^2$ and $({\mathbf {B}}_c,{\mathbf {B}}_d) \in V^2$ (with $a \ne b$ and $c \ne d$) we have:

$$\begin{aligned} \begin{aligned}&B_a \cap B_b \ne \emptyset \,,&B_a \cap B_b^{\text {c}} \ne \emptyset \,,\\&B_a \cap {\mathbf {B}}_c \ne \emptyset \,,&B_a \cap {\mathbf {B}}_c^{\text {c}} \ne \emptyset \,,\\&{\mathbf {B}}_c \cap {\mathbf {B}}_d^{\text {c}} \ne \emptyset \,.\\ \end{aligned} \end{aligned}$$

(1)

These conditions can be verified in polynomial time in a preprocessing step in order to avoid unnecessary computations (for example, we remove $B_2$ in $\varLambda$, if $B_1 \cap B_2^{\text {c}} = \emptyset$) or trivial solutions (for example, if $B_1 \cap B_2 = \emptyset$, then ${\mathcal {I}}\cap {\mathcal {U}}^{\text {c}} = \emptyset$).

Remark 2.1

We consider open balls $B_i$. This is useful in proofs because we get the set ${\mathcal {I}}\cap {\mathcal {U}}^{\text {c}}$ open. With closed balls $B_i$, the decision problem is the same.

2.2 A Standard Approach

We reformulate our geometric problem into a collection of q quadratically constrained quadratic programming (QCQP) : for $j = 1,\ldots ,q$,

$$\begin{aligned} P_0(j): \,\left\{ \begin{aligned}&\max _{x \in {\mathbb {R}}^n} (\Vert x-{\mathbf {c}}_{j}\Vert ^2 - {\mathbf {R}}_j^2)\,, \\&\hbox {such that} \,\, \Vert x-c_{i}\Vert ^2 - R_i^2 \le 0\,,\quad i =1,\ldots ,p\,,\\&\quad \quad \quad \quad \,\,\, \Vert x-{\mathbf {c}}_{k}\Vert ^2 - {\mathbf {R}}_k^2 \ge 0\,,\quad k =1,\ldots ,j-1\,.\\ \end{aligned} \right. \end{aligned}$$

(2)

We solve these problems sequentially for increasing integers j. Notwithstanding the difficult resolution of (2), the naive Algorithm 1 gives an exact response concerning the geometric inclusion ${\mathcal {I}} \subset {\mathcal {U}}$.

The feasible region ${\mathcal {X}}_j$ is the subset of points in ${\mathbb {R}}^n$ satisfying the constraints in problem $P_0(j)$. If the (nonempty) feasible region ${\mathcal {X}}_j$ for problem $P_0(j)$ is strictly included into ${\mathbf {B}}_j$, that is, $\Vert x-{\mathbf {c}}_{j}\Vert ^2-{\mathbf {R}}_j^2 <0$ for all $x \in {\mathcal {X}}_j$, then ${\mathcal {X}}_{j+1} = \emptyset$ and $\cup _{k=1}^{j}{\mathbf {B}}_k$ covers ${\mathcal {I}}$. Thus, Algorithm 1 tries to cover ${\mathcal {I}}$ with the balls in V, adding them one by one. The algorithm stops as soon as the feasible region becomes empty (justifying the while loop).

Other reformulations are possible. We choose one of them ensuring the feasibility of the considered problem at each step j. If feasibility is not required, solving $P_0(q)$ is enough work. In both cases, the non-convexity of the initial geometric problem is transferred to problems $P_0(j)$ for which the feasible regions (if $q>1$ and $j>1$) and the objective functions (with the standard formulation with a minimization) are nonconvex. For this reason, line search strategies for interior point methods can fail to converge toward the global optimum. On a simple example in Fig. 1, we highlight the failing of any point following methods.

Fig. 1

The dark blue region shows us that ${\mathcal {I}} \not \subset {\mathcal {U}}$. Solving $P_0(1)$ stucks the solution in the green region. If only continuous and feasible moves are allowed, as with an interior point method, we would fail to solve $P_0(2)$ as its feasible region is not connected

For decades, many approximate methods for the generic nonconvex QCQP problems (2) have been developed (see the review [12]) to avoid using primal methods. They are relaxation methods that usually convexify the nonconvex part of the problem or solve successive convex optimization approximate problems. Approaches as semi-definite relaxation (SDR) [13], reformulation linearization technique (RLT) [14] or successive convex approximation (SCA) [15, 16] are among the most popular. However, they are often computationally greedy (using $n^2$ unknowns) and only converge toward KKT stationary points.

We propose in this paper, to the best of our knowledge, the first exact and simple problem-solving method for the subclass of nonconvex QCQP problems involving only balls and complement of balls.

2.3 Proposed Solution

Our QCQP problem is specific as it only involves balls. We can take advantage of the fact that the intersection of two spheres, when they meet, belongs to an hyperplane. Considering a sphere ${\mathbf {S}}_j = \partial {\mathbf {B}}_j$, where $\partial (\cdot )$ denotes the frontier operator, we build hyperplanes as soon as a sphere $S_i = \partial B_i$ $(i=1,\ldots ,p)$ or ${\mathbf {S}}_k = \partial {\mathbf {B}}_k$ $(k \ne j,\, k =1,\ldots ,q)$ intersects ${\mathbf {S}}_j$. Each hyperplane defines a favored half-space. The intersection of the obtained half-spaces yields an open convex polyhedron $\texttt {P}_j$ which can be seen as a Voronoi-like structure (more details in Sect. 2).

The solution proposed in this paper is as follows. We introduce the notation ${\mathfrak {U}}_j = \cup _{k=1\,:\, k \ne j}^{q} {\mathbf {B}}_k$ and prove that we are able to detect an intersection between ${\mathcal {I}}$ and ${\mathbf {S}}_j \setminus {\mathfrak {U}}_j$ only by using the convex polyhedron $\texttt {P}_j$. This method is based on the set equality ${\mathbf {S}}_j \cap ({\mathcal {I}} \setminus {\mathfrak {U}}_j) = {\mathbf {S}}_j \cap \texttt {P}_j$. The closure of $\texttt {P}_j$ is denoted $\varPi _j$ $(\varPi _j =\overline{\texttt {P}}_j)$. Detection of a nonempty intersection ${\mathbf {S}}_j \cap \texttt {P}_j$ can be handled solving the following 2q (q for the minimum and q for the maximum) quadratic programs (QP): for $j = 1,\ldots ,q$,

$$\begin{aligned} P_1(j): \,\left\{ \begin{aligned}&{\mathrm{extr}}_{x \in {\mathbb {R}}^n} (\Vert x-{\mathbf {c}}_j\Vert ^2 - {\mathbf {R}}_j^2)\,, \\&\hbox {such that} \,\, x \in \varPi _j\,.\\ \end{aligned} \right. \end{aligned}$$

(3)

The minimum QP problem is tractable in polynomial time [17, 18]. Solving $P_1(j)$ for the maximum is a nonconvex (concave) problem, which can be solved by vertex enumeration in polynomial time if the polyhedron $\varPi _j$ is non-degenerate [19]. There exist particular cases, in practice rarely encountered, for which the vertex enumeration problem remains NP-hard [20].

In fact, as soon as we find a feasible point strictly inside the ball ${\mathbf {B}}_j$ and another one strictly outside, we have ${\mathbf {S}}_j \cap \texttt {P}_j \ne \emptyset$ and we will prove that we get ${\mathcal {I}} \setminus {\mathcal {U}} \ne \emptyset$.

If for all j, this intersection ${\mathbf {S}}_j \cap \texttt {P}_j$ is empty, we have ${\mathbf {S}}_j \cap ({\mathcal {I}} \setminus {\mathfrak {U}}_j) = {\mathcal {I}} \cap ( {\mathbf {S}}_j \setminus {\mathfrak {U}}_j) = \emptyset$ for all j, that is ${\mathcal {I}} \cap \partial {\mathcal {U}} = \emptyset$. Thus, with our method, we shift from the emptiness of the set ${\mathcal {I}} \setminus {\mathcal {U}}$ to the emptiness of the set ${\mathcal {I}} \cap \partial {\mathcal {U}}$. To solve the initial covering problem (${\mathcal {I}} \setminus {\mathcal {U}} = \emptyset$ ?), we notice that we only need to know a point inside ${\mathcal {I}}$ and test whether this point is also inside ${\mathcal {U}}$ to decide our question.

3 Equivalent Quadratic Programming

We now focus on the building of a unique polyhedron and show its close link with the initial nonconvex sets ${\mathcal {I}} \setminus {\mathfrak {U}}_q$. Finally, we show that the q polyhedra and their associated q quadratic programs solve the covering problem.

3.1 Linear Constraints

From now one, we consider a unique problem centered on the closed ball ${\mathbf {B}}_q$ and write ${\mathbf {B}} = {\mathbf {B}}_q$, ${\mathbf {c}} = {\mathbf {c}}_q$, ${\mathbf {R}} = {\mathbf {R}}_q$, $\texttt {P} = \texttt {P}_q$, $\varPi = \varPi _q$, ${\mathfrak {U}} = {\mathfrak {U}}_q$. For all $i \in \{1,\ldots ,p\}$ such that ${\mathbf {S}}= \partial {\mathbf {B}}$ and $S_i = \partial B_i$ intersect, we define the functions $h_i : {\mathbb {R}}^n \rightarrow {\mathbb {R}}$ as

$$\begin{aligned} h_i(x)= 2 \langle x ,{\mathbf {c}}-c_{i}\rangle - \Vert {\mathbf {c}}\Vert ^2 + \Vert c_{i} \Vert ^2 + {\mathbf {R}}^2-R_i^2\,. \end{aligned}$$

The associated hyperplane equation is $h_i(x)=0$ and we have the open half-space containing the set $B_i \setminus {\mathbf {B}}$: $H_i = \{x \in {\mathbb {R}}^n\,:\, h_i(x) < 0\}$. The geometric configuration of the balls ${\mathbf {B}}$ and $B_i$ with the half-space $H_i$ is given in Fig. 2 (left). All the balls in $\varLambda$ intersect ${\mathbf {B}}$, and the inclusion ${\mathbf {B}} \subset B_i$ is not excluded (see conditions (1)): in this case, we do not build any hyperplane.

Similar hyperplanes and half-spaces are built between spheres ${\mathbf {S}} = \partial {\mathbf {B}}$ and ${\mathbf {S}}_j = \partial {\mathbf {B}}_j$ for $j \in \{1,\ldots ,q-1\}$ when they intersect, but here, we consider the half-space containing ${\mathbf {B}} \setminus {\mathbf {B}}_j$. Thus, we define the functions ${\mathbf {h}}_j: {\mathbb {R}}^n \rightarrow {\mathbb {R}}$ such that

$$\begin{aligned} {\mathbf {h}}_j(x)= 2 \langle x, {\mathbf {c}}-{\mathbf {c}}_{j}\rangle -\Vert {\mathbf {c}}\Vert ^2+\Vert {\mathbf {c}}_{j}\Vert ^2 + {\mathbf {R}}^2-{\mathbf {R}}_j^2\,, \end{aligned}$$

and the associated hyperplane equation is ${\mathbf {h}}_j(x)=0$ with the open half-space ${\mathbf {H}}_j = \{x \in {\mathbb {R}}^n\,:\, -{\mathbf {h}}_j(x)< 0\}$. If ${\mathbf {B}} \cap {\mathbf {B}}_j = \emptyset$, a case not excluded in (1), we also do not build hyperplane.

Fig. 2

Left: half-space $H_i$ defined by the intersection of the spheres ${\mathbf {S}} = \partial {\mathbf {B}}$ and $S_i = \partial B_i$ and containing $B_i \setminus {\mathbf {B}}$. Right: example of feasible region $\varPi$ (the hatched area) with $p=1$ and $q=2$. Here, $\texttt {P}^+ = H_1$ and $\texttt {P}^- = {\mathbf {H}}_1$. The darker shade of blue is the subset of $\varPi$ lying inside the ball ${\mathbf {B}}$

With these half-spaces, we define the open convex polyhedron

$$\begin{aligned} \texttt {P} = \{x \in {\mathbb {R}}^n\,:\, h_i(x)< 0\,,\, -{\mathbf {h}}_j(x) < 0\,,\, i=1,\ldots ,p\,,\, j=1,\ldots ,q-1\} \end{aligned}$$

and the polyhedra $\texttt {P}^+ = \cap _{i=1}^p H_i$ and $\texttt {P}^- = \cap _{j=1}^{q-1} {\mathbf {H}}_j$ such that $\texttt {P} = \texttt {P}^+ \cap \texttt {P}^-$. The open polyhedron $\texttt {P}$ will be used to prove geometrical properties, whereas its closure, $\varPi = \overline{\texttt {P}}= \overline{\texttt {P}^+} \cap \overline{\texttt {P}^-} = \varPi ^+\cap \varPi ^-$, is the feasible region of the QP problem $P_1(q)$ with $\varPi ^+ = \overline{\texttt {P}^+}$ and $\varPi ^- = \overline{\texttt {P}^-}$.

An efficient resolution of the nonconvex problem of type $P_1$ (cf (3)) for maximum is made possible, solving for example a vertex enumeration problem [19]. An example of feasible region is drawn in Fig. 2 (right).

Before proving the equivalence of Problems (2) and (3), we present some simple equalities and inclusions used throughout this paper between sets involving balls and half-spaces.

Lemma 3.1

For $i \in \{1,\ldots ,p\}$ and $j \in \{1,\ldots ,q-1\}$, we have the relations:

$$\begin{aligned}&(a)\quad {\mathbf {S}}\cap B_i = {\mathbf {S}}\cap H_i\,,&(b)\quad {\mathbf {S}}\cap {\mathbf {B}}_j^{\text {c}} = {\mathbf {S}}\cap {\mathbf {H}}_j\,,\\&(c)\quad B_i \setminus {\mathbf {B}} \subset H_i\,,&(d)\quad {\mathbf {B}} \setminus {\mathbf {B}}_j \subset {\mathbf {H}}_j\,. \end{aligned}$$

The proof is straightforward.

3.2 Links Between the Polyhedron and the Initial Geometric Problem

We give a set equality linking the convex polyhedron $\texttt {P}$ and the open set ${\mathcal {I}} \setminus {\mathfrak {U}}$ involved in the initial geometric problem.

Corollary 3.1

${\mathbf {S}}\cap ({\mathcal {I}} \setminus {\mathfrak {U}}) = {\mathbf {S}}\cap \texttt {P}$.

Proof

${\mathbf {S}}\cap {\mathcal {I}} = {\mathbf {S}}\cap ( \cap _{i=1}^pB_i) = \cap _{i=1}^p ({\mathbf {S}}\cap B_i)=\cap _{i=1}^p ({\mathbf {S}}\cap H_i) = {\mathbf {S}}\cap (\cap _{i=1}^p H_i)= {\mathbf {S}}\cap \texttt {P}^+$ by relation (a) of Lemma 3.1. In the same way, we have ${\mathbf {S}}\cap {\mathfrak {U}}^{\text {c}} = {\mathbf {S}}\cap (\cup _{j=1}^{q-1} {\mathbf {B}}_j)^{\text {c}} = {\mathbf {S}}\cap (\cap _{j=1}^{q-1} {\mathbf {B}}_j^{\text {c}}) = \cap _{j=1}^{q-1}({\mathbf {S}} \cap {\mathbf {B}}_j^{\text {c}})=\cap _{j=1}^{q-1}({\mathbf {S}} \cap {\mathbf {H}}_j)= {\mathbf {S}}\cap \texttt {P}^-$ by De Morgan’s laws and relation (b) of Lemma 3.1. Therefore, ${\mathbf {S}}\cap {\mathcal {I}} \setminus {\mathfrak {U}} = ({\mathbf {S}}\cap {\mathcal {I}})\cap ({\mathbf {S}}\cap {\mathfrak {U}}^{\text {c}}) = ({\mathbf {S}}\cap \texttt {P}^+)\cap ({\mathbf {S}}\cap \texttt {P}^-) = {\mathbf {S}}\cap \texttt {P}$ and the relation is proven. $\square$

For $\epsilon \in {\mathbb {R}}$, we introduce the ball ${\mathbf {B}}^{R+\epsilon }$ with center ${\mathbf {c}}$ and radius ${\mathbf {R}}+\epsilon$. We also define ${\mathbf {S}}^{R+\epsilon } = \partial {\mathbf {B}}^{R+\epsilon }$. $V_n$ is the volume (Lebesgue measure) in dimension n. In the following proposition, we connect the position of points in the closed feasible region $\varPi$ to the spatial position of ${\mathcal {I}} \setminus {\mathfrak {U}}$.

Proposition 3.1

If the volume of the feasible region is nonzero ($V_n(\varPi )>0$), the following assertions are equivalent:

• (i) ${\mathbf {S}}\cap \texttt {P} \ne \emptyset$,

• (ii) there exists $(x^-, x^+)\in \varPi \times \varPi$ such that $\Vert x^--{\mathbf {c}}\Vert ^2< {\mathbf {R}}^2 < \Vert x^+-{\mathbf {c}}\Vert ^2$,

• (iii) $V_{n-1}({\mathbf {S}} \cap \varPi ) >0$ (the Lebesgue measure of the surface area is nonzero),

• (iv) there exists $r > 0$ such that, for all $\epsilon \in (-r,r)$, ${\mathbf {S}}^{R+\epsilon } \cap ({\mathcal {I}} \setminus {\mathfrak {U}}) \ne \emptyset$.

To state this result, we use the following lemma.

Lemma 3.2

With ${\mathcal {O}}$ an open set of ${\mathbb {R}}^n$, we have equivalence between propositions:

• (a) ${\mathbf {S}} \cap {\mathcal {O}} \ne \emptyset$;

• (b) $V_{n-1}({\mathbf {S}} \cap {\mathcal {O}}) >0$;

• (c) there exists $r > 0$ such that, for all $\epsilon \in (-r,r)$, ${\mathbf {S}}^{R+\epsilon } \cap {\mathcal {O}} \ne \emptyset$.

Proof

With ${\tilde{x}} \in {\mathbf {S}} \cap {\mathcal {O}}$, there exists an open ball $B({\tilde{x}},\rho )$ centered on ${\tilde{x}}$ and of radius $\rho$, such that $B({\tilde{x}},\rho ) \subset {\mathcal {O}}$. Thus, $V_{n-1}({\mathbf {S}} \cap {\mathcal {O}}) \ge V_{n-1}({\mathbf {S}} \cap B({\tilde{x}},\rho )) >0$ and for all $\epsilon \in (-\rho ,\rho )$, ${\mathbf {S}}^{R+\epsilon } \cap {\mathcal {O}}\subset {\mathbf {S}}^{R+\epsilon } \cap B({\tilde{x}},\rho ) \ne \emptyset$. We have shown that $a) \implies b) \implies c)$. The implication $c) \implies a)$ is obvious, and Lemma is proven. $\square$

Proof of Proposition 3.1

The implication $i) \implies ii)$ is due to the openness of $\texttt {P}$. We prove the converse. As $V_n(\varPi )>0$ and $\varPi$ is convex, we have $\texttt {P} \ne \emptyset$ and $\overline{\texttt {P}}=\varPi$. Thus, there exist sequences $(x_n^-)$ and $(x_n^+)$ such that $\lim _{n \rightarrow +\infty } x_n^- = x^-$ and $\lim _{n \rightarrow +\infty } x_n^+ = x^+$ with $x_n^-,x_n^+ \in \texttt {P}$ for all $n \in {\mathbb {N}}$. Therefore, there exists $N\in {\mathbb {N}}$ such that, for all $n \ge N$, $\Vert x_n^--{\mathbf {c}}\Vert ^2< {\mathbf {R}}^2 < \Vert x_n^+-{\mathbf {c}}\Vert ^2$. By convexity of $\texttt {P}$, the segment $[x_n^-,x_n^+]$ is in $\texttt {P}$ and ${\mathbf {S}} \cap [x_n^-,x_n^+] \ne \emptyset$ and we get ${\mathbf {S}} \cap \texttt {P} \ne \emptyset$. We use the Lemma 3.2 ($a \iff b$) with the open set $\texttt {P}$ to prove the equivalence between i) and iii), knowing that $V_{n-1}({\mathbf {S}} \cap \varPi )= V_{n-1}({\mathbf {S}} \cap \texttt {P})$. As ${\mathbf {S}}\cap ({\mathcal {I}} \setminus {\mathfrak {U}}) = {\mathbf {S}}\cap \texttt {P}$ (see Corollary 3.1), we use again Lemma 3.2 ($b \iff c$) with the open set ${\mathcal {I}} \setminus {\mathfrak {U}}$ to get the equivalence between propositions iii) and iv). $\square$

With this last result, we have shown that some propositions involving the closed polyhedron $\varPi$ are related to results using $\texttt {P}$ and hence ${\mathcal {I}} \setminus {\mathfrak {U}}$. We now combine these results with the q quadratic programming problems to solve the problem.

3.3 Quadratic Programming Decision

We still focus on a unique quadratic program:

$$\begin{aligned} P_1(q) = P_1: \,\left\{ \begin{aligned}&{\mathrm{extr}}_{x \in {\mathbb {R}}^n} (\Vert x-{\mathbf {c}}\Vert ^2 - {\mathbf {R}}^2)\,, \\&\hbox {such that} \,\, x \in \varPi \,,\\ \end{aligned} \right. \end{aligned}$$

(4)

and we denote by $x^*_{min}$ the value of the argument x for which the objective function attains its minimum over the set $\varPi$. If $\varPi$ is bounded, $x^*_{max}$ is one value of the argument x for which the objective function attains its maximum. Notice that $x^*_{max}$ is not necessarily unique, hence the use of “one value” in previous sentence. If $\varPi$ is unbounded, we consider thereafter that $\Vert x^*_{max}-{\mathbf {c}}\Vert ^2 = +\infty$, even if $x^*_{max}$ is not well-defined.

The non-existence of a point $x^-$ or $x^+$ satisfying the strict inequalities in Proposition 3.1 case (ii) is related to the resolution of problem $P_1$. For example, there is no point $x^-$ if ${\mathbf {R}}^2 \le \Vert x^*_{min}-{\mathbf {c}}\Vert ^2$. Before solving this extremum problem, one should verify the feasibility of the constraints. Studying the feasibility of these constraints, we get some inclusion criteria.

Proposition 3.2

If $V_n(\varPi ^+) = 0$, then ${\mathcal {I}} \subset {\mathbf {B}}$ (or ${\mathcal {I}} = \emptyset$),

if $V_n(\varPi ^-) = 0$, then ${\mathbf {B}} \subset {\mathfrak {U}}$,

if $V_n(\varPi ) = 0$, then ${\mathcal {I}}\cap ({\mathbf {S}} \setminus {\mathfrak {U}}) = \emptyset$.

Proof

${\mathcal {I}} \setminus {\mathbf {B}} = \cap _{i=1}^{p}(B_i \setminus {\mathbf {B}}) \subset \cap _{i=1}^{p} H_i = \texttt {P}^+$ using relation (c) of Lemma 3.1. If $V_n(\varPi ^+) = 0$, then $\texttt {P}^+ = \emptyset$ and we have ${\mathcal {I}} \subset {\mathbf {B}}$. With relation (d) of Lemma 3.1, ${\mathbf {B}} \setminus {\mathfrak {U}} = \cap _{j=1}^{q-1}({\mathbf {B}} \setminus {\mathbf {B}}_j) \subset \cap _{j=1}^{q-1} {\mathbf {H}}_j = \texttt {P}^-$. If $V_n(\varPi ^-) = 0$, then $\texttt {P}^- = \emptyset$ and we have ${\mathbf {B}} \subset {\mathfrak {U}}$. The last result is a direct application of Corollary 3.1. $\square$

We can now present our main result, showing the equivalent between the resolution of the QP problems $P_1(j)$, $j=1,\ldots ,q$, and the decision about ${\mathcal {I}} \setminus {\mathcal {U}}$.

Theorem 3.1

If $V_n(\varPi )>0$, we have the following results.

• (A) If there exists $(x^-, x^+)\in \varPi \times \varPi$ such that $\Vert x^--{\mathbf {c}}\Vert ^2< {\mathbf {R}}^2 < \Vert x^+-{\mathbf {c}}\Vert ^2$, then ${\mathcal {I}} \setminus {\mathcal {U}} \ne \emptyset$, $V_n({\mathcal {I}} \setminus {\mathcal {U}})>0$ and $V_n({\mathcal {I}} \cap {\mathcal {U}})>0$;

• (B) if ${\mathbf {R}}^2 \le \Vert x^*_{min}-{\mathbf {c}}\Vert ^2$ or $\Vert x^*_{max}-{\mathbf {c}}\Vert ^2 \le {\mathbf {R}}^2$, then ${\mathcal {I}} \cap ({\mathbf {S}}\setminus {\mathfrak {U}}) = \emptyset$.

Proof

In case (A), Proposition 3.1 gives the existence of $r > 0$ and $x \in {\mathbb {R}}^n$ such that $x \in {\mathbf {S}}^{R+\frac{r}{2}} \cap ({\mathcal {I}} \setminus {\mathfrak {U}})$. In particular, $x \in {\mathbf {S}}^{R+\frac{r}{2}}$, then $x \in {\mathbf {B}}^{\text {c}}$. Consequently, $x \in ({\mathcal {I}} \setminus {\mathfrak {U}}) \cap {\mathbf {B}}^{\text {c}} = {\mathcal {I}} \setminus {\mathcal {U}}$ (an open set) and $V_n({\mathcal {I}} \setminus {\mathcal {U}}) > 0$. With a point $x' \in {\mathbf {S}}^{R-\frac{r}{2}}\cap ({\mathcal {I}} \setminus {\mathfrak {U}})$, we get ${\mathbf {B}} \cap {\mathcal {I}} \ne \emptyset$ and $V_n({\mathcal {I}} \cap {\mathcal {U}}) > 0$. Case (B) is the negation of case (A). That is, there exists $r>0$ such that for all $\epsilon \in (0,r)$ or for all $\epsilon \in (-r,0)$, we have ${\mathbf {S}}^{R+\epsilon } \cap ({\mathcal {I}} \setminus {\mathfrak {U}}) = \emptyset$ using Proposition 3.1. Therefore, ${\mathcal {I}} \cap ({\mathbf {S}}\setminus {\mathfrak {U}}) = \emptyset$. Otherwise, with ${\mathcal {O}} = {\mathcal {I}} \setminus {\mathfrak {U}}$ in Lemma 3.2 we get ${\mathbf {S}}^{R+\epsilon } \cap ({\mathcal {I}} \setminus {\mathfrak {U}}) \ne \emptyset$ for all $\epsilon \in (-r^*,r^*)$ and fixed $r^* > 0$, which is impossible. $\square$

If case (B) is satisfied, the convex set ${\mathcal {I}}$ does not intersect the frontier ${\mathbf {S}}\setminus {\mathfrak {U}}$ and we consider another reference ball in V to solve a new $P_1$-type problem (3). If for all elements of V we get case (B), we have ${\mathcal {I}} \cap \partial {\mathcal {U}} = \emptyset$. Using a point ${\hat{x}}$ in ${\mathcal {I}}$, we test whether ${\hat{x}}$ is included in ${\mathcal {U}}$ to conclude.

4 Simplifications

4.1 Convex Reduction

We show that, if some mild conditions are satisfied, the feasible region $\varPi$ of Problem $P_2$ (see (4)) can be unbounded and the maximum problem in Theorem 3.1 does not have to be solved anymore. The problem is reduced to a convex quadratic programming problem, which can be solved in polynomial time [17, 18].

Theorem 4.1

For all $i \in \{1,\ldots ,p\}$ and $j \in \{1,\ldots ,q-1\}$, if $R_i^2 < {\mathbf {R}}^2+\Vert {\mathbf {c}}-c_i\Vert ^2$ and ${\mathbf {R}}_j^2 > {\mathbf {R}}^2+\Vert {\mathbf {c}}-{\mathbf {c}}_j\Vert ^2$, then $\varPi \setminus {\mathbf {B}} \ne \emptyset$ or $\varPi = \emptyset$.

Proof

First, we show that ${\mathbf {c}} \not \in \varPi$. Indeed, we have for $i = 1,\ldots ,p$,

$$\begin{aligned} h_i({\mathbf {c}}) = \langle 2{\mathbf {c}} - ({\mathbf {c}} + c_{i}),{\mathbf {c}}-c_{i}\rangle + ({\mathbf {R}}^2-R_i^2) = {\mathbf {R}}^2 + \Vert {\mathbf {c}}- c_i\Vert ^2 - R_i^2 > 0\,, \end{aligned}$$

and for $j = 1,\ldots ,q-1$,

$$\begin{aligned} -{\mathbf {h}}_j({\mathbf {c}})= -\langle 2{\mathbf {c}} - ({\mathbf {c}}+{\mathbf {c}}_{j}),{\mathbf {c}}-{\mathbf {c}}_{j}\rangle - ({\mathbf {R}}^2-{\mathbf {R}}_j^2) = {\mathbf {R}}_j^2 - {\mathbf {R}}^2 - \Vert {\mathbf {c}}- {\mathbf {c}}_j\Vert ^2 > 0\,, \end{aligned}$$

using the hypothesis. Second, we prove that, if $\varPi \ne \emptyset$, then $\varPi$ is unbounded. Suppose that there exists ${\hat{x}} \in \varPi$; we have ${\mathbf {c}}-{\hat{x}}\ne 0$. We consider the affine functions $g_i : \lambda \mapsto h_i({\hat{x}}+\lambda ({\mathbf {c}}-{\hat{x}}))$ and ${\mathbf {g}}_i : \lambda \mapsto -{\mathbf {h}}_i({\hat{x}}+\lambda ({\mathbf {c}}-{\hat{x}}))$ with $\lambda \in {\mathbb {R}}$. We have $g_i(0)\le 0$, $g_i(1)> 0$ and ${\mathbf {g}}_i(0)\le 0$, ${\mathbf {g}}_i(1)> 0$, so that these functions are strictly increasing. Thus, for all negative lambda, we have ${\hat{x}}+\lambda ({\mathbf {c}}-{\hat{x}}) \in \varPi$. Therefore, as $\lim _{\lambda \rightarrow -\infty } \Vert {\hat{x}}+\lambda ({\mathbf {c}}-{\hat{x}})\Vert = +\infty$, the set $\varPi \setminus {\mathbf {B}}$ cannot be empty. $\square$

With only an upper bound on the number of involved balls in $\varLambda \cup V$, we have the same result.

Proposition 4.1

If the number of constraints is less or equal to the dimension, that is $p+q-1 \le n$, then $\varPi$ is unbounded (or empty) and the conclusion of Theorem 4.1 still holds.

Proof

We explicit the constraints as a system of linear inequalities, $Ax \le ~b$, with $A \in {\mathbb {R}}^{(p+q-1)\times n}$ and $b \in {\mathbb {R}}^{p+q-1}$. If the rank of A is equal to n, the system $Ax = b - t {\mathbb {I}}$, with ${\mathbb {I}}$ the vector filled by ones, has a (unique) solution x(t) and $\lim _{t\rightarrow +\infty }\Vert x(t)\Vert = \lim _{t\rightarrow +\infty }\Vert A^{-1}(b - t {\mathbb {I}})\Vert = +\infty$ with $Ax(t) = b~-~t{\mathbb {I}}~\le ~b$ for positive t. If $rank(A) < n$, the rank-nullity theorem shows that the linear subspace Ker(A) is of dimension $n-rank(A)>0$ and then $Ker(A) \ne \{0\}$. If a point $x_0 \in {\mathbb {R}}^n$ satisfies the inequalities, thus, $A(x_0+ty) = Ax_0 \le b$, with $y \in Ker(A) \setminus \{0\}$ and $t\in {\mathbb {R}}$. We have $\lim _{t\rightarrow +\infty }\Vert x_0+ty\Vert = +\infty$, and the result is proven. $\square$

Remark 4.1

The conditions of Theorem 4.1 are sharp. If one of the relations is false, then there exist sets of balls $\varLambda$ and V with $\#(\varLambda \cup V)= p+q = n+2$, such that we have $\varPi \subset {\mathbf {B}}$. An example of such a set $\varPi$ is the n-dimensional pyramid with summit near point ${\mathbf {c}}$ and a basis obtained with the only one hyperplane that do not satisfies the conditions of Theorem 4.1. The necessary condition of Proposition 4.1 is also not verified as $p+q = n + 2 > n +1$.

Theorem 4.2

If there exists $d \in {\mathbb {R}}^n \setminus \{0\}^n$ such that $\langle d, {\mathbf {c}}-c_{i} \rangle < 0$ and $\langle d, {\mathbf {c}}-{\mathbf {c}}_{j} \rangle > 0$ for all $i \in \{1,\ldots ,p\}$ and $j \in \{1,\ldots ,q-1\}$ (linear separability), then $\varPi$ is unbounded or $\varPi = \emptyset$.

Proof

Suppose that there exist ${\hat{x}} \in \varPi$ and d satisfying the condition of the theorem. Then for all $\alpha < 0$, we have for all the constraints

$$\begin{aligned} h_i({\hat{x}} + \alpha d)= & {} 2 \langle {\hat{x}},{\mathbf {c}}-c_{i}\rangle + 2\alpha \langle d,{\mathbf {c}}-c_{i}\rangle -\Vert {\mathbf {c}}\Vert ^2+\Vert c_{i}\Vert ^2 + ({\mathbf {R}}^2-R_i^2) \le h_i({\hat{x}}) \le 0\,,\\ {\mathbf {h}}_j({\hat{x}} + \alpha d)= & {} 2\langle {\hat{x}},{\mathbf {c}}-{\mathbf {c}}_j\rangle + 2 \alpha \langle d,{\mathbf {c}}-{\mathbf {c}}_j\rangle - \Vert {\mathbf {c}}\Vert ^2+\Vert {\mathbf {c}}_j\Vert ^2 + ({\mathbf {R}}^2-{\mathbf {R}}_j^2) \ge {\mathbf {h}}_j({\hat{x}}) \ge 0\,, \end{aligned}$$

and ${\hat{x}} + \alpha d$ defines an infinite direction inside the polyhedron $\varPi$. $\square$

All these results are important for our changepoint detection algorithm (see “Appendix A”) as they can considerably reduce the computation time.

4.2 The Concave QCQP Problem

If there is only one ball in the set V and then no more concave constraint in (2), we consider only one QCQP problem of type (2) and only one QP problem of type (4) ($q=1$). We say that we solve a concave QCQP problem, because we minimize the opposite of a convex function over a set of convex constraints.

A first direct consequence is that $\varPi = \varPi ^+$, $\varPi ^- = {\mathbb {R}}^n$ and ${\mathfrak {U}}=\emptyset$. In this particular configuration, some of our results in Sects. 3 and  4.1 can be simplified.

Feasibility:

If $V_n(\varPi ) = 0$, then ${\mathcal {I}} \subset {\mathbf {B}}$ (or ${\mathcal {I}} = \emptyset$).

Quadratic programming reduction:

(A) If $(x^-, x^+)\in \varPi \times \varPi$ is such that $\Vert x^--{\mathbf {c}}|\Vert ^2< {\mathbf {R}}^2 < \Vert x^+-{\mathbf {c}}\Vert ^2$, then ${\mathcal {I}} \setminus {\mathbf {B}} \ne \emptyset$;

(B) if ${\mathbf {R}}^2 \le \Vert x^*_{min}-{\mathbf {c}}\Vert ^2$, then ${\mathcal {I}} \cap {\mathbf {S}} = \emptyset$;

(C) if $\Vert x^*_{max}-{\mathbf {c}}\Vert ^2 \le {\mathbf {R}}^2$, then ${\mathcal {I}} \subset {\mathbf {B}}$.

Proof

Only the case (C) has to be proven. Using Lemma 3.1, we have ${\mathcal {I}} \setminus {\mathbf {B}} = \cap _{i=1}^p (B_i \setminus {\mathbf {B}}) \subset \cap _{i=1}^p (H_i \setminus {\mathbf {B}}) = \varPi \setminus {\mathbf {B}}$. However, $\varPi \setminus {\mathbf {B}} = \emptyset$ and then ${\mathcal {I}} \subset {\mathbf {B}}$. $\square$

Convex optimization reduction:

if $R_i^2 < {\mathbf {R}}^2+\Vert {\mathbf {c}}-c_i\Vert ^2$, for all $i \in \{1,\ldots ,p\}$, then $\varPi \setminus {\mathbf {B}} \ne \emptyset$ or $\varPi = \emptyset$.

5 Simulations

Algorithm 2 describes our new procedure based on equivalent QP problems. It is made of two steps: the detection of an intersection between ${\mathcal {I}}$ and $\partial {\mathcal {U}}$ using QP problems (see Sect. 3) and the test ${\mathcal {I}} \subset {\mathcal {U}}$ with a unique point (if ${\mathcal {I}} \cap \partial {\mathcal {U}} = \emptyset$). We chose to determine $x^*_{min}$ and $x^*_{max}$ for each QP problem but, in fact, we only need points $x^-$ and $x^+$, as shown by Theorem 3.1.

Our goal is to compare the performances of this algorithm against Algorithm 1 on two aspects: the exactness of the result and their computational efficiency. We will also illustrate the polynomial time complexity of our new algorithm by increasing the dimension n at fixed p and q.

We have implemented¹ Algorithm 1 in Python using the recent (2017) suggest and improve method for nonconvex QCQP [12] based on packages ’cvxpy’ [21] and its extension ’qcqp’. This allows us to use state-of-the-art methods on Python, more elaborated than interior point one, which is not adapted to our problem (see Fig. 1). The suggest method is set to random and the improve step to ADMM (alternating directions method of multipliers [22]) followed by a coordinate descent step. This is the most efficient combination of methods (empirically speaking) and is used in some examples given in the package.

The center points for balls are randomly generated with a normal distribution centered on zero with standard deviation $\sigma = 10$, and their radius is the distance to zero plus a quantity $\epsilon = 5$ for intersection ball and $2\epsilon$ for union balls. We also verify that the obtained balls intersect each other as in (1), if not, we simulate new balls. Examples of simulated data are shown in Fig. 3.

Fig. 3

Two examples of simulated data with $p = q = 3$ in dimension 2. On the left, ${\mathcal {I}} \not \subset {\mathcal {U}}$, on the right ${\mathcal {I}} \subset {\mathcal {U}}$. The opaque red disks are the balls of the union set V. The transparent blue disks are the balls of the intersection set $\varLambda$

In Table 1, we generate 100 examples for each proposed configuration. We first consider examples with ${\mathcal {I}} \not \subset {\mathcal {U}}$. In case $(n=2, p =3)$, we compare the results of the two algorithms with the 2d graphical representation of the balls problem to confirm the exactness of our method.

Algorithm 2 always finds the exact result in dimension 2, and we get the value 100. For higher dimensions, we know the result of Algorithm 2 to be exact (as shown by theoretical results of Sect. 3) and count the number of identical results between the two algorithms to get the number of true results for Algorithm 1. Algorithm 1 often fails, in particular when the non-inclusion is difficult to visually detect (obtained on a small volume). This behavior is a consequence of our simulations: we generated data with a unique simulation procedure, so that, for increasing q it becomes harder to generate examples without inclusion. An increasing dimension n gives more space to get a non-inclusion and facilitate the detection of ${\mathcal {I}} \not \subset {\mathcal {U}}$ for Algorithm 1.

In the case of the inclusion ${\mathcal {I}} \subset {\mathcal {U}}$, we notice that Algorithm 1 always finds the right answer in our simulations. Interestingly, the resolution of the unique problem $P_0(q)$ often fails, unlike the non-inclusion case.

Table 1 Number of exact results over 100 simulations

In Table 2, we highlight the efficiency of our new algorithm, compared with the Python package ’qcqp’ based on nonconvex QCQP methods. Notice that improvements in the code for Algorithm 2 are still possible with a direct implementation of the QP problem stopping as soon as we get $x^-$ or $x^+$ and in the vertex enumeration solver (we simply used package cdd² [23]). We have made 10 simulations ($i= 1,\ldots ,10$) for 3 configurations ($n = 5, 10, 20$) with $p=q=3$ in case ${\mathcal {I}} \not \subset {\mathcal {U}}$ (simpler to obtain in our ball generation algorithm with increasing dimension n). Our results show for Algorithm 1 a computational time complexity of order $O(10^3)$ slower than for Algorithm 2 and a higher time variability between iterates.

Table 2 Comparison of execution time with $p=q=3$ and varying dimension n

An empirical polynomial time complexity is confirmed by our simulations as shown in Fig. 4. Simulations have been performed with ${\mathcal {I}} \not \subset {\mathcal {U}}$ for an increasing n, so that, in these simulations, we only solve a unique QP problem for maximum and minimum to detect an intersection. With a linear regression based on the model $t = an^b$, we get a power of about $b = 1.76$ with $R^2 = 0.935$ in the logarithmic scale.

Fig. 4

Left: $p = q= 3$ and $n = 10,20,30,\ldots ,2000$. Each datapoint is the mean over 10 identical simulations in case ${\mathcal {I}} \not \subset {\mathcal {U}}$. A unique QP problem is solved for each simulation. Right: in the log-log scale, the curve stabilizes, corroborating a polynomial time complexity of type $an^b$. A linear model returns a coefficient of determination of 0.935 with $b \approx 1.76$

6 Conclusions

The geometric question of the cover of an intersection of balls by an union of other balls has been addressed using optimization tools. The collection of nonconvex quadratically constrained quadratic programming problems has been transformed into a collection of quadratic optimization problems: the minimum and the maximum distances between a point and a Voronoi-like polyhedron has to be found for each problem. The maximum problem can be handled efficiently by vertex enumeration. If simple conditions are satisfied, the polyhedron is unbounded, the maximization problem has not to be considered anymore, and the complexity is known to be in polynomial time. Simulations show that state-of-the-art nonconvex QCQP algorithms, developed in Python, often fail the decision test and are computationally greedy. Our new method never fails (is exact) and efficiently finds the solution with a time complexity of order $O(10^3)$ smaller in our simulation study. In a further work, we will apply this method to the efficient implementation of a multidimensional changepoint detection algorithm based on pruned dynamic programming.

Appendices

Appendices

Motivation

Our covering problem has a direct application for the implementation of the pruned penalized³ dynamic programming algorithm for changepoint detection in a multidimensional setting [25,26,27]. This problem consists in finding the optimal changepoint within the set ${\mathbb {S}}_m = \{\tau =(\tau _1,\ldots ,\tau _k) \in {\mathbb {N}}^k \,|\, 1 = \tau _0< \tau _1< \cdots< \tau _k < m+1 = \tau _{k+1}\}$ such that we minimize a quadratic (for Gaussian modelization) penalized cost (by $\beta >0$):

$$\begin{aligned} Q_m= & {} \min _{\tau \in {\mathbb {S}}_m}\left[ \sum _{i=0}^{k}\lbrace {\mathcal {C}}(y_{\tau _i:\tau _{i+1}-1}) + \beta \rbrace \right] \,,\\ \hbox {with}\quad {\mathcal {C}}(y_{\tau _i:\tau _{i+1}-1})= & {} \min _{x \in {\mathbb {R}}^n} \sum _{j=\tau _i}^{\tau _{i+1}-1} \sum _{k=1}^{n}(x_k- y_{jk})^2\,, \end{aligned}$$

and $(y_1,\ldots ,y_m)^T \in ({\mathbb {R}}^n)^m$ the data to segment. Using a dynamic programming procedure, we build the recursion $Q_{t+1}(x) = \min \lbrace Q_{t}(x),\, m_{t}+\beta \rbrace + \sum _{k=1}^{n}(x_k- y_{(t+1)k})^2$ with $m_t = \min _{x} Q_t(x)$ and the initialization $Q_0(x) = 0$. We solve this recursion iteratively from $t=0$ to $t=m-1$.

At each t, the recursive function $Q_t(\cdot )$ is a piecewise quadratic function defined on t non-overlapping regions $R^1_t,\ldots ,R^t_t \subset {\mathbb {R}}^n$, for which each quadratics is active on a set $R^i_t$ of type “${\mathcal {I}}\setminus {\mathcal {U}}$”. Precisely,

$$\begin{aligned} \begin{aligned}&R_t^1 = \cap _{i=1}^t B_i^1\,, \\&R_t^2 = \cap _{i=2}^t B_i^2 \setminus B_1^1\,, \\&R_t^3 = \cap _{i=3}^t B_i^3 \setminus (B_2^1 \cup B_2^2)\,, \\&\quad \quad \vdots \\&R_t^t = R_t^t \setminus (\cup _{j=1}^{t-1}B_{t-1}^j)\,.\\ \end{aligned} \end{aligned}$$

where all the “$B_l^k$” sets designate balls determined by the data $(y_k,\ldots ,y_l)$. At the next iteration $t+1$, each $R_t^i$ is intersected by a new ball (that is, we add a ball in each ${\mathcal {I}}$) and the set $R_{t+1}^{t+1}$ is created.

In order to get the global minimum $m_t$, we compare the minima of all present quadratics. To speed-up the procedure, it is worthwhile to search for vanishing sets, that is to detect efficiently the emptiness of sets $R_t^1,\ldots ,R_t^t$. In fact, once a set is proved to be empty, we do not need to consider its minimum anymore at any further iteration. This method is called pruning in the changepoint detection literature.

In a paper in preparation, we will compare this exact method to heuristic approaches in order to build a fast algorithm for an application to genomic data. Moreover, our methods can be extended to other distributions of the natural exponential family.

An Alternative Method

In some applications, as for example in “Appendix A,” we need to test sequentially the covering. This means that we add at each iteration a new ball in the intersection ${\mathcal {I}}$. For large q, it could be expensive to solve q QP problems at each iteration for minimum and maximum. Another approach consists in detecting an intersection between ${\mathcal {I}}\setminus {\mathcal {U}}$ and ${\mathbb {S}}$ (as soon as $\#{\mathcal {I}} >0$), where ${\mathbb {S}}$ is the frontier of the new ball ${\mathbb {B}}$ (with center c and radius R) to add in ${\mathcal {I}}$. The problem is now centered on the “newest” ball of set $\varLambda$ rather than the successive balls of V. Thus, a unique QP problem centered on the ball ${\mathbb {B}}$ is built and we get a result similar to Theorem 3.1:

Theorem B.1

If $V_n(\varPi )>0$, we have the following results.

• (a) If there exists $(x^-, x^+)\in \varPi \times \varPi$ such that $\Vert x^--c\Vert ^2< R^2 < \Vert x^+-c\Vert ^2$,

  then $({\mathbb {B}} \cap {\mathcal {I}}) \setminus {\mathcal {U}} \ne ~\emptyset$ and $V_n(({\mathbb {B}} \cap {\mathcal {I}}) \setminus {\mathcal {U}}) > 0$;

• (b) if $R^2 \le \Vert x^*_{min}-c\Vert ^2$ or $\Vert x^*_{max}-c\Vert ^2 \le R^2$, then ${\mathbb {S}}\cap ({\mathcal {I}}\setminus {\mathcal {U}}) = \emptyset$.

In case (b), we can conclude knowing a point ${\tilde{x}}_k$ for each connected component $C_k$ $(k=1,\ldots ,K)$ of ${\mathcal {I}}\setminus {\mathcal {U}}$ and testing ${\tilde{x}}_k \in {\mathbb {B}}$. If always false, we get $({\mathbb {B}} \cap {\mathcal {I}}) \setminus {\mathcal {U}} = \emptyset$. The drawback of this approach is the necessity to know the number of connected components in ${\mathcal {I}}\setminus {\mathcal {U}}$. However, with the conditions of Theorem 4.1 the set ${\mathcal {I}}\setminus {\mathcal {U}}$ is connected (see the proof) and a unique point in ${\mathcal {I}}\setminus {\mathcal {U}}$ is required $(K = 1)$.

Proposition 3.2 remains the same with ${\mathbb {B}}$ instead of ${\mathbf {B}}$. The detection of the inclusion ${\mathcal {I}} \subset {\mathbb {B}}$ is now made possible and is important for sequential problems, since in this case, the ball ${\mathbb {B}}$ is not added to the set $\varLambda$.