1 Introduction

The maximum box problem receives as input a finite point set in \({\mathbb {R}}^d\), where each point is associated with a positive or negative weight, and outputs an axis-aligned rectangle (i.e., box) such that the sum of the weights of the points that it contains is maximized [3]. We consider this problem on a recent uncertainty model in which each element of the input has assigned a probability. Particularly, each point has assigned its own and independent probability of being present in the final (hence random) point set. Then, one can ask the following questions: What is the probability that for the final point set there exists a box that covers a weight sum greater than or equal to a given parameter? What is the expectation of the maximum weight sum that can be covered with a box? Uncertainty models come from real scenarios in which large amounts of data, arriving from many sources, have inherent uncertainty. In computational geometry, we can find several recent works on uncertain point sets such as: the expected total length of the minimum Euclidean spanning tree [5]; the probability that the distance between the closest pair of points is at least a given parameter [11]; the computation of the most-likely convex hull [16]; the probability that the area or perimeter of the convex hull is at least a given parameter [15]; the smallest enclosing ball [9]; the probability that a 2-colored point set is linearly separable [10]; the area of the minimum enclosing rectangle [17]; and Klee’s measure of random rectangles [20]. We deal with the maximum box problem in the above mentioned random model. The maximum box problem is a geometric combinatorial optimization problem, different from most of the problems considered in this random setting that are computations of some measure or structure of the extent of the geometric objects.

For \(d=1\), the maximum box problem asks for an interval of the line. If the points are uncertain as described above, then it is equivalent to consider as input a sequence of random numbers, where each number has two possible outcomes: zero if the number is not present and the actual value of the number otherwise. The output is the subsequence of consecutive numbers with maximum sum. We consider the simpler case when the subsequence is a partial sum, that is, it contains the first (or leftmost) number of the sequence. More formally: We say that a random variable X is zero-value if \(X=v\) with probability \(\rho \), and \(X=0\) with probability \(1-\rho \), for an integer number \(v=v(X)\ne 0\) and a probability \(\rho \). We refer to v as the value of X and to \(\rho \) as the probability of X. In any sequence of zero-value variables, all variables are assumed to be mutually independent. Let \(\mathcal{X}=X_1,X_2,\ldots ,X_n\) be a sequence of n mutually independent zero-value variables, whose values are \(a_1,a_2,\ldots ,a_n\), respectively. We study the random variable

$$\begin{aligned} {\mathsf {S}}({{\mathcal {X}}})~=~\max \{0,X_1,X_1+X_2,\ldots ,X_1+\cdots +X_n\}, \end{aligned}$$

which is the maximum partial sum of the random sequence \({{\mathcal {X}}}\). The fact that \({\mathbb {E}}[\max \{X,Y\}]\) is not necessarily \(\max \{{\mathbb {E}}[X],{\mathbb {E}}[Y]\}\), even if X and Y are independent random variables, makes hard the computation of the expectation \({\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}})]\).

Kleinberg et al. [13] proved that the problem of computing \(\Pr [X_1+\cdots +X_n>1]\) is #P-complete, in the case where the values of the variables \(X_1,X_2,\ldots ,X_n\) are all positive. The proof can be straightforwardly adapted to also show that computing \(\Pr [X_1+\cdots +X_n>z]\) is #P-complete, where the values of \(X_1,X_2,\ldots ,X_n\) are all positive, for any fixed \(z>0\). This last fact implies that computing \(\Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z]\) for any fixed \(z\ge 1\) is #P-hard. We show hardness results when the probabilities of \(X_1,X_2,\ldots ,X_n\) are the same, and their values are not necessarily positive. Namely, we prove (Sect. 2.1) that computing \(\Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z]\) for any fixed \(z\ge 1\), and computing the expectation \({\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}})]\) are both #P-hard problems, even if all variables of \({{\mathcal {X}}}\) have the same less-than-one probability. When \(a_1,a_2,\ldots ,a_n\in [-a..b]\) for bounded \(a,b\in {\mathbb {N}}\), we show (Sect. 2.2) that both \(\Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z]\) and \({\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}})]\) can be computed in time polynomial in n, a, and b. For two integers \(u<v\), we use [u..v] to denote the set \(\{u,u+1,\ldots ,v\}\).

For \(d=2\), we consider the maximum box problem in the context of red and blue points, where red points have weight \(+1\) and blue points weight \(-\infty \). Let R and B be disjoint finite point sets in the plane with a total of n points, where the elements of R are colored red and the elements of B are colored blue. The maximum box problem asks for a box H such that \(|H\cap R|\) is maximized subject to \(|H\cap B|=\emptyset \). This problem has been well studied, with algorithms whose running times go from \(O(n^2\log n)\) [6], \(O(n^2)\) [3], to \(O(n \log ^3 n)\) [2]. Let \(S\subseteq R\cup B\) be the random point set where every point \(p\in R\cup B\) is included in S independently and uniformly at random with probability \(\pi (p)\in [0,1]\). Let \(\mathsf {box}(S)\) denote the random variable equal to the maximum number of red points in S that can be covered with a box not covering any blue point of S.

We prove (Sect. 3.1) that computing the probability \(\Pr [\mathsf {box}(S)\ge k]\) for any given \(k\ge 2\), and computing the expectation \({\mathbb {E}}[\mathsf {box}(S)]\), are both #P-hard problems. We further show (Sect. 3.2) that given a point o of the plane, computing the probability that there exists a box containing exactly two red points of S, no blue point of S, and the point o can be solved in polynomial time. If we remove the restriction of containing o, this problem is also #P-hard. This fact is a direct consequence of the previous #P-hardness proofs.

In all running time upper bounds in this paper, in both algorithms and reductions, we assume a real RAM model of computation where each arithmetic operation on large-precision numbers takes constant time. Otherwise, the running times should be multiplied by a factor proportional to the bit complexity of the numbers, which is polynomial in n and the bit complexity of the input probability values [5, 11].

2 Weighted Points

2.1 Hardness

Theorem 1

For any integer \(z\ge 1\) and any \(\rho \in (0,1)\), the following problem is #P-hard: Given a sequence \({{\mathcal {X}}}=X_1,X_2,\ldots ,X_n\) of n zero-value random variables, each with probability \(\rho \), compute \(\Pr [{\mathsf {S}}({{\mathcal {X}}}) \ge z]\).

Proof

Let \(z\ge 1\) be an integer, and \(\rho \in (0,1)\) be a probability. We show a Turing reduction from the #SubsetSum problem, which is known to be #P-complete [8]. Our reduction assumes an unknown algorithm (i.e., oracle) \(\mathcal {A}({{\mathcal {X}}})\) computing \(\Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z]\) for any finite sequence \(\mathcal{X}\) of zero-value random variables, that will be called twice. #SubsetSum receives as input a set \(\{a_1,\ldots ,a_n\}\subset {\mathbb {N}}\) of n numbers and a target \(t\in {\mathbb {N}}\), and counts the number of subsets \(J\subseteq [1..n]\) such that \(\sum _{j\in J}a_j=t\). It remains #P-hard if the subsets J must also satisfy \(|J|=k\), for given \(k\in [1..n]\). Let \((\{a_1,\ldots ,a_n\},t,k)\) be an instance of this #SubsetSum, in which we assume \(t\le a_1+\dots +a_n\).

Let \(m=\max \{z,1+a_1+\dots +a_n\}>t\), and \(\mathcal{X}=X_0,X_1,X_2,\ldots ,X_n\) be a sequence of \(n+1\) zero-value random variables, each with probability \(\rho \), where the value of \(X_0\) is \(-km-t+z\), and the value of \(X_i\) is \(m+a_i\) for every \(i\in [1..n]\). Observe that for \(J\subseteq [1..n]\) we have

$$\begin{aligned} \sum _{j\in J}(m+a_j)= km+t ~\Leftrightarrow ~ \left( \sum _{j\in J}a_j= t~\text {and}~|J|=k\right) . \end{aligned}$$

Furthermore, \(|J|>k\) implies \(\sum _{j\in J}(m+a_j)> km+t\).

Let \(J_{{{\mathcal {X}}}}=\{j\in [1..n]:X_j\ne 0\}\), and for any s, let

$$\begin{aligned} N_s ~=~ \left| J\subseteq [1..n]:|J|=k,\sum \nolimits _{j\in J}a_j\ge s\right| . \end{aligned}$$

Then, #SubsetSum asks for \(N_t-N_{t+1}\). Call \(\mathcal {A}({{\mathcal {X}}})\) to compute \(\Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z]\). Then:

$$\begin{aligned} \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z]&~=~ \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z, X_0=0] + \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z, X_0=-km-t+z] \end{aligned}$$

where,

$$\begin{aligned} \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z, X_0=0]&~=~ \Pr [X_0=0] \cdot \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z\mid X_0=0] \\&~=~ (1-\rho ) \cdot \Pr [|J_{{{\mathcal {X}}}}|\ge 1] ~=~ (1-\rho ) \cdot \left( 1 - \Pr \left[ |J_{{{\mathcal {X}}}}|=0\right] \right) \\&~=~ (1-\rho ) \cdot (1 - (1-\rho )^n), \end{aligned}$$

and

$$\begin{aligned}&\Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z, X_0=-km-t+z] \\&\quad =~ \Pr [X_0=-km-t+z] \cdot \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z\mid X_0=-km-t+z ] \\&\quad =~ \rho \cdot \Pr \left[ -km -t +z + \sum _{j\in J_{{{\mathcal {X}}}}}(m+a_j)\ge z\right] \\&\quad = \rho \cdot \Pr \left[ \sum _{j\in J_{{{\mathcal {X}}}}}(m+a_j)\ge km+t\right] \\&\quad =~ \rho \cdot \left( \Pr \left[ |J_{{{\mathcal {X}}}}|=k,\sum _{j\in J_{{{\mathcal {X}}}}}(m+a_j)\ge km+t\right] \right. \\&\qquad \quad +\left. \sum _{i=k+1}^n\Pr \left[ |J_{{{\mathcal {X}}}}|=i,\sum _{j\in J_{{{\mathcal {X}}}}}(m+a_j)\ge km+t\right] \right) \\&\quad =~ \rho \cdot \Pr \left[ |J_{{{\mathcal {X}}}}|=k,\sum _{j\in J_{{{\mathcal {X}}}}}a_j\ge t\right] + \rho \cdot \sum _{i=k+1}^n\Pr [|J_{{{\mathcal {X}}}}|=i] \\&\quad =~ \rho \cdot N_t \cdot \rho ^k\cdot (1-\rho )^{n-k} + \rho \cdot \sum _{i=k+1}^n\left( {\begin{array}{c}n\\ i\end{array}}\right) \cdot \rho ^i\cdot (1-\rho )^{n-i}. \end{aligned}$$

Hence, we can compute \(N_t\) in polynomial time from the value of \(\Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z]\). Consider now the random sequence \(\mathcal{X}'=X_0',X_1,X_2,\ldots ,X_n\), where \(X_0'\) has value \(-km-(t+1)+z\). Using arguments similar to those above, by calling \(\mathcal {A}({{\mathcal {X}}}')\) to compute \(\Pr [{\mathsf {S}}({{\mathcal {X}}}')\ge z]\), we can compute \(N_{t+1}\) in polynomial time from this probability. Then, \(N_t-N_{t+1}\) can be computed in polynomial time, plus the time of calling twice the oracle \(\mathcal {A}\). This implies the theorem. \(\square \)

Theorem 2

For any \(\rho \in (0,1)\), the following problem is #P-hard: Given a sequence \({{\mathcal {X}}}=X_1,\ldots ,X_n\) of n zero-value random variables, each with probability \(\rho \), compute \({\mathbb {E}}[{\mathsf {S}}(\mathcal{X})]\).

Proof

Let \({{\mathcal {X}}}=X_1,X_2,\ldots ,X_n\) be a sequence of zero-value random variables, each with probability \(\rho \), and consider the sequence \({{\mathcal {X}}}'=X_0,X_1,\ldots ,X_n\), where \(X_0\) is a zero-value random variable with value \(-1\) and probability \(\rho \). Let w be the sum of the positive values among the values of \(X_1,\ldots ,X_n\). Then:

$$\begin{aligned} {\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}})] ~=~ \sum _{i=1}^w i\cdot \Pr [{\mathsf {S}}({{\mathcal {X}}})=i] ~=~ \sum _{i=1}^w \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge i], \end{aligned}$$

and

$$\begin{aligned} {\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}}')]&~=~ \sum _{i=1}^w \Pr [{\mathsf {S}}({{\mathcal {X}}}')\ge i] \\&~=~ \sum _{i=1}^w(\Pr [{\mathsf {S}}({{\mathcal {X}}}')\ge i,X_0=0] + \Pr [{\mathsf {S}}({{\mathcal {X}}}')\ge i,X_0=-1]) \\&~=~ \sum _{i=1}^w(\Pr [X_0=0]\cdot \Pr [{\mathsf {S}}({{\mathcal {X}}}')\ge i\mid X_0=0] ~ \\&\qquad +\Pr [X_0=-1]\cdot \Pr [{\mathsf {S}}({{\mathcal {X}}}')\ge i\mid X_0=-1]) \\&~=~ \sum _{i=1}^w((1-\rho )\cdot \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge i] + \rho \cdot \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge i+1]) \\&~=~ \sum _{i=1}^w(1-\rho )\cdot \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge i] + \sum _{i=2}^{w+1} \rho \cdot \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge i] \\&~=~ (1-\rho )\cdot \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge 1] + \sum _{i=2}^{w}\Pr [{\mathsf {S}}({{\mathcal {X}}})\ge i]. \end{aligned}$$

Then, we have that

$$\begin{aligned} {\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}})] - {\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}}')] ~=~ \rho \cdot \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge 1]. \end{aligned}$$

Since computing \(\Pr [{\mathsf {S}}({{\mathcal {X}}})\ge 1]\) is #P-hard (Theorem 1), then computing \({\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}})]\) is also #P-hard via a Turing reduction. \(\square \)

2.2 Pseudo-Polynomial Time Algorithms

Let \({{\mathcal {X}}}=X_1,X_2,\ldots ,X_n\) be a sequence of n zero-value random variables, with values \(a_1,a_2,\ldots ,a_n\in [-a..b]\subset {\mathbb {Z}}\) and probabilities \(\rho _1,\rho _2,\ldots ,\rho _n\), respectively, for some \(a,b\in {\mathbb {N}}\). We show that both \(\Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z]\) and \({\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}})]\) can be computed in time polynomial in n, a, and b. Let \(J = \{j\in [1..n]:a_j<0\}\) and

$$\begin{aligned} w_0 ~=~ \sum _{j\in J}|a_j| ~=~ O(na) ~~\text {and}~~ w_1 ~= \sum _{j\in [1..n]\setminus J}a_j ~=~ O(nb). \end{aligned}$$

For every \(t\in [1..n]\), let

$$\begin{aligned} S_t&~=~ X_1+\cdots +X_t,~~M_t ~=~ \max \{0,S_1,S_2,\ldots ,S_t\},~~\text {and} \\ L_t&~=~ \{\Pr [M_t=k,S_t=s]:k\in [0..w_1],s\in [-w_0..w_1],k\ge s \}. \end{aligned}$$

Observe that \(L_t\) has size \(O(w_1(w_0+w_1))=O(nb(na+nb))=O(n^2b(a+b))\) for every t, and that \(L_1\) can be trivially computed. Using the dynamic programming algorithm design paradigm, we next show how to compute the values of \(L_t\), \(t\ge 2\), assuming that all values of \(L_{t-1}\) have been computed. Note that:

$$\begin{aligned} \Pr [M_t=k,S_t=s]&= \Pr [M_t=k,S_t=s,X_t=0] + \Pr [M_t=k,S_t=s,X_t=a_t], \end{aligned}$$

where

$$\begin{aligned} \Pr [M_t=k,S_t=s,X_t=0]&~=~ \Pr [X_t=0]\cdot \Pr [M_t=k,S_t=s\mid X_t=0] \\&~=~ (1-\rho _t)\cdot \Pr [M_{t-1}=k,S_{t-1}=s] \end{aligned}$$

and

$$\begin{aligned} \Pr [M_t=k,S_t=s,X_t=a_t]&~=~ \Pr [X_t=a_t]\cdot \Pr [M_t=k,S_t=s\mid X_t=a_t] \\&~=~ \rho _t \cdot \Pr [M_t=k,S_t=s\mid X_t=a_t]. \end{aligned}$$

When \(k=s\), we have for \(a_t<0\) that \(\Pr [M_t=k,S_t=s\mid X_t=a_t]=0\), since this event indicates that \(S_t=X_1+\cdots +X_t\) is a maximum partial sum of \(X_1,\ldots ,X_t\), but this cannot happen because any maximum partial sum ends in a positive element. For \(a_t>0\) we have

$$\begin{aligned} \Pr [M_t=k,S_t=s\mid X_t=a_t]&~=~ \Pr [M_{t-1}\le k,S_{t-1}=s-a_t] \\&~=~ \sum _{i=s-a_t}^k \Pr [M_{t-1}= i,S_{t-1}=s-a_t]. \end{aligned}$$

When \(k>s\), \(M_t\) does not count the element \(a_t\), hence \(M_{t-1}=M_{t}\). Then

$$\begin{aligned} \Pr [M_t=k,S_t=s\mid X_t=a_t]&~=~ \Pr [M_{t-1}= k,S_{t-1}=s-a_t]. \end{aligned}$$

Modeling each set \(L_t\) as a 2-dimensional table (or array), note that each value of \(L_t\) can be computed in \(O(k-(s-a_t))=O(w_1)\) time, and hence all values of \(L_t\) can be computed in \(O(w_1)\cdot O(n^2b(a+b))=O(n^3b^2(a+b))\) time. Finally, once all the values of \(L_n\) have been computed in \(O(n)\cdot O(n^3b^2(a+b))=O(n^4b^2(a+b))\) time, we can compute \(\Pr [{\mathsf {S}}(\mathcal{X})\ge z]\) as

$$\begin{aligned} \Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z]&~=~ \sum _{k=z}^{w_1}\Pr [{\mathsf {S}}(\mathcal{X})=k] ~=~ \sum _{k=z}^{w_1}\sum _{s=-w_0}^k\Pr [M_n=k,S_n=s] \end{aligned}$$

in \(O(w_1(w_0+w_1))=O(n^2b(a+b))\) time, and \({\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}})]\) as

$$\begin{aligned} {\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}})] ~=~ \sum _{z=1}^{w_1}\Pr [{\mathsf {S}}({{\mathcal {X}}})\ge z] \end{aligned}$$

in \(O(w_1)=O(nb)\) time. As a consequence, we get the following result.

Theorem 3

Let \({{\mathcal {X}}}=X_1,X_2,\ldots ,X_n\) be a sequence of n zero-value random variables, with values \(a_1,a_2,\ldots ,a_n\in [-a..b]\subset {\mathbb {Z}}\) and probabilities \(\rho _1,\rho _2,\ldots ,\rho _n\), respectively, for some \(a,b\in {\mathbb {N}}\). Then, both \(\Pr [{\mathsf {S}}(\mathcal{X})\ge z]\) and \({\mathbb {E}}[{\mathsf {S}}({{\mathcal {X}}})]\) can be computed in time polynomial in n, a, and b.

3 Red and Blue Points

3.1 Hardness

Given a graph \(G=(V,E)\), a subset \(V'\subseteq V\) is an independent set of G if no pair of vertices of \(V'\) define an edge in E. Let N(G) denote the number of independent sets of G. The problem #IndSet of counting the number of independent sets in a graph is #P-complete, even if the graph is planar, bipartite, and with maximum degree 4 [18]. We show in what follows a one-to-many Turing reduction from #IndSet to the problem of computing \(\Pr [\mathsf {box}(S)\ge k]\), for any given \(k\ge 2\). The proof uses techniques similar to that of Kamousi et al. [11] to prove that counting vertex covers in weighted unit-disk graphs is #P-hard, and that of Vadhan [18] to prove that counting weighted matchings in planar bipartite graphs is #P-hard.

Let \(G=(V,E)\) be the input of #IndSet, where G is a planar, bipartite graph with maximum degree 4. Let \(n=|V|\) and \(m=|E|=O(n)\). For an overview of the whole proof, refer to Fig. 1.

Fig. 1
figure 1

Given an instance \(G=(V,E)\) of #IndSet, for every s in the set \(\{h,h+1,\ldots ,h+m\}\) of \(m+1\) integers polynomially bounded in n, we construct the random colored point set \(R_s\cup B_s\). Let \(G_s\) be the graph obtained from G by subdividing each edge with exactly s new vertices. Assuming that an oracle computes \(\Pr [\mathsf {box}(S)\ge 2]\), where \(S\subseteq R_s\cup B_s\) is the random sample, we show that \(N(G_s)\) can be computed in constant time from this probability. From all of the values \(N(G_{h}),N(G_{h+1}),\ldots ,N(G_{h+m})\) already computed, we show that N(G) can be computed in polynomial time

Full size image

For any subset \(V'\subseteq V\) and any edge \(e=\{u,v\}\in E\), we say that \(V'\) 1-covers edge e if exactly one of u and v belongs to \(V'\). We also say that \(V'\) 2-covers e if both u and v belong to \(V'\). Let \(C_{i,j}\) denote the number of subsets of V that 1-cover exactly i edges and 2-cover exactly j edges. Then,

$$\begin{aligned} N(G)~=~\sum _{i=0}^m C_{i,0}. \end{aligned}$$

For \(s\ge 1\), let \(G_s=(V_s,E_s)\) be the graph obtained from G by adding exactly s intermediate vertices on each edge of E. Let \(\{f_i\}_{i=1}^{\infty }\) be the Fibonacci sequence, with \(f_1=f_2=1\) and \(f_{i}=f_{i-1}+f_{i-2}\) for \(i\ge 3\). Let \(\alpha _i=f_{i+1}/f_{i+2}\) for \(i\ge 0\). The next lemma relates the number \(N(G_s)\) of independent sets of \(G_s\) to the values \(C_{i,j}\) in G.

Lemma 4

We have

$$\begin{aligned} N(G_s) ~=~ (f_{s+2})^m \cdot \sum _{0\le i+j\le m} C_{i,j} \cdot (\alpha _s)^i \cdot (1-\alpha _s)^j. \end{aligned}$$

Proof

Any independent set \(V'_s\subseteq V_s\) of \(G_s\) induces the subset \(V'_s\cap V\) of V, which is not necessarily an independent set of G because it may 2-cover some edges. Let \(V'\subseteq V\) be any subset of V that 1-covers i edges and 2-covers j edges. For any edge \(e\in E\), let \(p_e\) denote the path induced by the s vertices added to e when constructing \(G_s\) from G. An independent set of \(G_s\) inducing \(V'\) can be obtained by starting with \(V'\) and adding vertices in the following way. For every edge \(e=\{u,v\}\in E\):

  1. (1)

    if \(V'\) neither 1-covers nor 2-covers e, then add any independent set of \(p_e\).

  2. (2)

    if \(V'\) 1-covers e, say \(u\in V'\), then add any independent set of \(p_e\) not containing the extreme vertex of \(p_e\) adjacent to u in \(G_s\).

  3. (3)

    if \(V'\) 2-covers e, then add any independent set of \(p_e\) with no extreme vertex.

It is well known that the number of independent sets of a path of length \(\ell \) is exactly \(f_{\ell +3}\) [18]. Since \(p_e\) has length \(s-1\) for every e, the number of choices for cases (1), (2), and (3) are \(f_{s+2}\), \(f_{s+1}\), and \(f_s\), respectively. Therefore, the number of independent sets of \(G_s\) inducing a subset of V that 1-covers i edges and 2-covers j edges is precisely \(C_{i,j} \cdot (f_{s+1})^i \cdot (f_s)^j \cdot (f_{s+2})^{m-i-j}\). Hence, the number \(N(G_s)\) of independent sets of \(G_s\) satisfies

$$\begin{aligned} N(G_s)&~=~ \sum _{0\le i+j\le m} C_{i,j} \cdot (f_{s+1})^i \cdot (f_s)^j \cdot (f_{s+2})^{m-i-j} \\&~=~ (f_{s+2})^m \cdot \sum _{0\le i+j\le m} C_{i,j} \cdot \left( \frac{f_{s+1}}{f_{s+2}}\right) ^i \cdot \left( \frac{f_{s}}{f_{s+2}}\right) ^j \\&~=~ (f_{s+2})^m \cdot \sum _{0\le i+j\le m} C_{i,j} \cdot \left( \frac{f_{s+1}}{f_{s+2}}\right) ^i \cdot \left( 1-\frac{f_{s+1}}{f_{s+2}}\right) ^j \\&~=~ (f_{s+2})^m \cdot \sum _{0\le i+j\le m} C_{i,j} \cdot (\alpha _s)^i \cdot (1-\alpha _s)^j, \end{aligned}$$

which completes the proof. \(\square \)

Lemma 5

Let T be a set of \(m+1\) integers, each bounded by a polynomial in n. If we know the value of \(N(G_s)\) for every \(s\in T\), then the number N(G) can be computed in time polynomial in n.

Proof

For every \(s\in T\), the value of \((f_{s+2})^m\) can be computed in \(O(\log s + \log m)=O(\log n)\) time, and the value of \(\alpha _s\) also in \(O(\log s)=O(\log n)\) time. Let \(b_s=N(G_s)/(f_{s+2})^m\) for every \(s\in T\). Consider the polynomial

$$\begin{aligned} P(x) ~=~ \sum _{0\le i+j\le m} C_{i,j} \cdot x^i \cdot (1-x)^j ~=~ a_0 + a_1 x + a_2 x^2 + \dots + a_m x^m, \end{aligned}$$

of degree m, whose coefficients \(a_0,a_1,\ldots ,a_m\) are linear combinations of the terms \(C_{i,j}\). By Lemma 4, and using the known values of \(b_s\) and \(\alpha _s\) for every \(s\in T\), we have \(m+1\) evaluations of P(x) of the form \(b_s=P(\alpha _s)\), each corresponding to the linear equation \(b_s = a_0 + a_1 \cdot \alpha _s + a_2\cdot \alpha _s^2 + \dots + a_m\cdot \alpha _s^m\) with variables the coefficients \(a_0,a_1,\ldots ,a_m\). The main matrix of this system of \(m+1\) linear equations is Vandermonde, with parameters \(\alpha _s\) for every \(s\in T\). All \(\alpha _s\) are distinct (refer to [18] or Appendix A for completeness), so the determinant of the main matrix is non-zero, and the system has a unique solution \(a_0,a_1,\ldots ,a_m\), which can be computed in time polynomial in n. Finally, observe that for \(j=0\), the coefficient of the polynomial \(P(x)=C_{i,j} \cdot x^i \cdot (1-x)^j = C_{i,0} \cdot x^i\) is \(C_{i,0}\). Furthermore, for \(j>0\), all the coefficients of the polynomial

$$\begin{aligned} P(x) ~= & {} ~ C_{i,j} \cdot x^i \cdot (1-x)^j ~\\= & {} ~ C_{i,j}\cdot x^i \cdot \left( \left( {\begin{array}{c}j\\ 0\end{array}}\right) -\left( {\begin{array}{c}j\\ 1\end{array}}\right) x^1+\left( {\begin{array}{c}j\\ 2\end{array}}\right) x^2 - \dots + (-1)^j\left( {\begin{array}{c}j\\ j\end{array}}\right) x^j\right) \end{aligned}$$

sum up to zero. Indeed, it suffices to note that \(P(1)=0\). Hence, we obtain

$$\begin{aligned} a_0 + a_1 + a_2 + \dots + a_m ~=~ \sum _{i=0}^m C_{i,0} ~=~ N(G). \end{aligned}$$

which shows that N(G) can be computed in time polynomial in n. \(\square \)

In polynomial time, the graph \(G=(V,E)\) can be embedded in the plane using \(O(n^2)\) area in such a way that its vertices are at integer coordinates, and its edges are drawn so that they are polylines made up of line segments of the form \(x= i\) or \(y =j\), for integers i and j [19] (see Fig. 2a). Let \(h=O(n)\) be the maximum number of bends of the polylines corresponding to the edges.

Fig. 2
figure 2

a An embedding of G. b The embedding of \(G_s\) for \(s=2\): two intermediate vertices are added to each edge of G so that all polyline bends are covered

Full size image

For \(s=h,h+1,\ldots ,h+m\), we embed the graph \(G_s\) in the following way. We embed the graph G as above; scale the embedding by factor \(2(s+1)\); and for each edge of G, add s intermediate vertices to the polyline of the edge so that they have even integer coordinates and cover all bends of the polyline (see Fig. 2b). Then, each edge of \(G_s\) is represented in the embedding by a vertical or horizontal segment. Let the point set \(R_0=R_0(s)\subset {\mathbb {Z}}^2\) denote the vertex set of the embedding, and color these points in red. By translation if necessary, we can assume \(R_0\subset [0..N]^2\) for some \(N=O(n^2)\). Let \(B_0=B_0(s)\) be the following set of blue points: For each horizontal or vertical line \(\ell \) through a point of \(R_0\), and each two consecutive points \(p,q\in R_0\) in \(\ell \) such that the vertices p and q are not adjacent in \(G_s\), we add a blue point in the segment pq connecting p and q, in order to “block” this segment, so that the blue point has one odd coordinate. In this way, blue points blocking horizontal segments have odd x-coordinates and even y-coordinates; and blue points blocking vertical segments have even x-coordinates and odd y-coordinates. Hence, a blue point cannot block at the same time a horizontal and a vertical segment defined by two red points. Note that \(|B_0|=O(|R_0|)=O(n+m\cdot s)=O(n^2)\). Now, a horizontal or vertical segment connecting two points p and q of \(R_0\cup B_0\) represents an edge of \(G_s\) if and only if \(p,q\in R_0\) and the segment does not contain any other point of \(R_0\cup B_0\) in its interior (see Fig. 4).

We perturb \(R_0\cup B_0\subset [0..N]^2\) to obtain a point set with rational coordinates by applying the function \(\lambda :[0..N]^2\rightarrow {\mathbb {Q}}^2\), where

$$\begin{aligned} \lambda (p)=\left( x(p)+\frac{x(p)+y(p)}{4N+1},y(p)+\frac{x(p)+y(p)}{4N+1}\right) , \end{aligned}$$

to every \(p\in R_0\cup B_0\), where x(p) and y(p) denote the x- and y-coordinates of p, respectively. Similar perturbations can be found in [1, 4], and refer to Fig. 3. Since \(\lambda \) is injective [4], let \(\lambda ^{-1}\) denote the inverse of \(\lambda \). For \(A\subset [0..N]^2\), let \(\lambda (A)=\{\lambda (p)\mid p\in A\}\), and for \(A'\subset \lambda ([0..N]^2)\) let \(\lambda ^{-1}(A')=\{\lambda ^{-1}(p)\mid p\in A'\}\). Let \(\delta =1/(4N+2)\), and define the sets

$$\begin{aligned} R_s ~=~ \lambda (R_0) ~~\text {and}~~ B_s ~=~ \lambda (B_0) \cup \left\{ p+(1/2,1/2),p+(\delta ,-\delta )\mid p\in R_s\right\} . \end{aligned}$$

To simplify the notation, let \(R=R_s\) and \(B=B_s\). Note that \(|R|=O(n^2)\) and \(|B|=O(n^2)\). For two points a and b, let D(a, b) be the box with the segment ab as a diagonal. The proof of the next technical lemma is deferred to Appendix B.

Fig. 3
figure 3

The way in which points are perturbed using function \(\lambda \)

Full size image
Fig. 4
figure 4

The point set \(R_0\cup B_0\) for the embedding \(G_s\), \(s=2\), depicted in Fig. 2b. The grid lines are equally spaced in two units, then their intersection points have even coordinates. After the perturbation with the function \(\lambda \) (see Fig. 3), the extra blue points \(\{p+(1/2,1/2),p+(\delta ,-\delta )\mid p\in R_s\}\) are included in \(B_s\) to avoid that the box \(D(\lambda (p),\lambda (q))\) contains no blue point, for any two points \(p,q\in R_0\) which do not belong to the same edge of the embedding. See for example the points p and q, denoted in the figure (Color figure online)

Full size image

Lemma 6

For any different \(p,q\in R\), the vertices \(\lambda ^{-1}(p)\) and \(\lambda ^{-1}(q)\) are adjacent in \(G_s\) if and only if the box D(p, q) contains no point of B.

Theorem 7

Given \(R\cup B\), it is #P-hard to compute \(\Pr [\mathsf {box}(S)\ge k]\) for every integer \(k\ge 2\), and it is also #P-hard to compute \({\mathbb {E}}[\mathsf {box}(S)]\).

Proof

Let \(k=2\). Assume that there exists an algorithm (i.e., oracle) \(\mathcal {A}\) that computes \(\Pr [\mathsf {box}(S)\ge 2]\). Consider the planar bipartite graph \(G=(V,E)\), with maximum degree 4, the input of #IndSet. Let \(T=\{h,h+1,\ldots ,h+m\}\). For each \(s\in T\) we create the graph \(G_s\), embed \(G_s\) in the plane, and build the colored point set \(R\cup B=R_s\cup B_s\) from this embedding. For each red point \(p\in R\) we set its probability \(\pi (p)\) to 1/2, and for each blue point \(q\in B\) we set \(\pi (q)=1\). Note from Lemma 6 that there does not exist any box containing more than two red points of R and no blue point from B. Then, we have \(\Pr [\mathsf {box}(S)\ge 2]=\Pr [\mathsf {box}(S)= 2]\), where \(S\subseteq R\cup B\) is the random subset of \(R\cup B\). Furthermore,

$$\begin{aligned} \Pr [\mathsf {box}(S)= 2]= & {} \Pr [\lambda ^{-1}(S\cap R)~\text {is not an independent set in}~G_s] \\= & {} 1 - \Pr [\lambda ^{-1}(S\cap R)~\text {is an independent set in}~G_s] \\= & {} 1 - \frac{N(G_s)}{2^{|R|}} \\ N(G_s)= & {} 2^{|R|}\cdot (1-\Pr [\mathsf {box}(S)\ge 2]). \end{aligned}$$

Then, for each \(s\in T\) we can compute \(N(G_s)\) by calling \(\mathcal {A}\) once. By Lemma 5, we can compute N(G) from the \(m+1\) computed values of \(N(G_s)\) for each \(s\in T\). Hence, it is #P-hard to compute \(\Pr [\mathsf {box}(S)\ge 2]\) via a Turing reduction from #IndSet. To show that computing \({\mathbb {E}}[\mathsf {box}(S)]\) is also #P-hard, for each \(s\in T\) consider the above point set \(R\cup B\) and note that

$$\begin{aligned} {\mathbb {E}}[\mathsf {box}(S)]= & {} 1\cdot \Pr [\lambda ^{-1}(S\cap R)~\text {is an independent set in}~G_s,S\cap R\ne \emptyset ] + \\&2\cdot \Pr [\lambda ^{-1}(S\cap R)~\text {is not an independent set in}~G_s] \\= & {} \frac{N(G_s)-1}{2^{|R|}} + 2\cdot \left( 1 - \frac{N(G_s)}{2^{|R|}}\right) ~=~ 2 - \frac{N(G_s)+1}{2^{|R|}} \\ N(G_s)= & {} 2^{|R|} \cdot (2-{\mathbb {E}}[\mathsf {box}(S)]) - 1. \end{aligned}$$

Let now \(k\ge 3\). For each \(s\in T\), the graph \(G_s\) can be colored with two colors, 0 and 1, because it is also a bipartite graph. Each red point in R corresponds to a vertex in \(G_s\). Then, for each red point \(p\in R\) with color 0 we add new \(\lfloor \frac{k}{2} \rfloor -1\) red points close enough to p (say, at distance much smaller than \(\delta \)), and for each red point \(q\in R\) with color 1 we add new \(\lceil \frac{k}{2} \rceil -1\) red points close enough to q. Let \(R'=R'(s)\) be the set of all new red points, and assign \(\pi (u)=1\) for every \(u\in R'\). In this new colored point set \(R\cup R'\cup B\), there is no box containing more than k red points and no blue point. Furthermore, every box containing exactly k red points and no blue point contains two points \(p,q\in R\) such that \(\lambda ^{-1}(p)\) and \(\lambda ^{-1}(q)\) are adjacent in \(G_s\); and for every \(p,q\in R\) such that \(\lambda ^{-1}(p)\) and \(\lambda ^{-1}(q)\) are adjacent in \(G_s\) such a box containing p and q exists. Then, when taking \(S\subseteq R\cup R'\cup B\) at random, we also have

$$\begin{aligned} \Pr [\mathsf {box}(S)\ge k]= & {} \Pr [\mathsf {box}(S)= k] \\= & {} \Pr [\lambda ^{-1}(S\cap R)~\text {is not an independent set in}~G_s] \\= & {} 1 - \frac{N(G_s)}{2^{|R|}}. \end{aligned}$$

Hence, computing \(\Pr [\mathsf {box}(S)\ge k]\) is also #P-hard for any \(k\ge 3\). \(\square \)

3.2 Two-Point Boxes

From the proof of Theorem 7, note that it is also #P-hard to compute the probability that in \(S\subseteq R\cup B\) there exists a box that contains exactly two red points p, q and no blue point; and that this box can be restricted to be the minimum box D(p, q) having p and q as opposed vertices. In this section, we present a polynomial-time algorithm to compute such a probability when the box is further restricted to contain a given point \(o\notin R\cup B\) of the plane in the interior. We assume general position, that is, there are no two points of \(R\cup B\cup \{o\}\) with the same x- or y-coordinate. We further assume w.l.o.g. that o is the origin of coordinates.

Given a fixed \(X\subseteq R\cup B\), and \(S\subseteq R\cup B\) chosen at random, let \(E(X)=E(X,S)\) be the event that there exist two red points \(p,q\in S\cap X\) such that the box D(p, q) contains the origin o, no other red point in \(S\cap X\), and no blue in \(S\cap X\). Then, our goal is \(\Pr [E(R\cup B)]\).

Theorem 8

Given \(R\cup B\), \(\Pr [E(R\cup B)]\) can be computed in polynomial time.

Proof

Let \(X\subseteq R\cup B\), and define \(X^+=\{p\in X\mid y(p)>0\}\) and \(X^-=\{p\in X\mid y(p)<0\}\). Given points \(q\in X^+\) and \(r\in X^-\), define the events

$$\begin{aligned} U_q(X,S) = \left[ q=\arg \min _{p\in X^+\cap S}\{y(p)\}\right] ~~\text {and}~~ W_r(X,S) = \left[ r=\arg \max _{p\in X^-\cap S}\{y(p)\}\right] . \end{aligned}$$

Let \(U_q(X)=U_q(X,S)\) and \(W_r(X)=W_r(X,S)\). Using the formula of the total probability, we have:

$$\begin{aligned} \Pr [E(X)]= & {} \sum _{q\in X^+}\Pr \left[ E(X)\mid U_q(X)\right] \cdot \Pr \left[ U_q(X)\right] \\= & {} \sum _{q\in X^+}\Pr \left[ E(X)\mid U_q(X)\right] \cdot \left( \pi (q) \cdot \prod _{p\in X^+:y(p)<y(q)}(1-\pi (p)) \right) . \end{aligned}$$

To compute \(\Pr \left[ E(X)\mid U_q(X)\right] \), we assume \(x(q)>0\). The case where \(x(q)<0\) is symmetric. If \(q\in B\), then observe that when restricted to the event \(U_q(X)\) any box \(D(p',q')\) defined by two red points \(p',q'\in S\cap X\), containing the origin o and no other red point in \(S\cap X\), where one between \(p'\) and \(q'\) is to the right of q, will contain q. Hence, we must “discard” all points to the right of q, all points between the horizontal lines through q and o because they are not present, and q itself. Then, we have that:

$$\begin{aligned} \Pr \left[ E(X)\mid U_q(X)\right] ~=~ \Pr [E(X_q)], \end{aligned}$$

where \(X_q\subset X\) contains the points \(p\in X\) such that \(x(p)<x(q)\) and either \(y(p)>y(q)\) or \(y(p)<0\). If \(q\in R\), we expand \(\Pr \left[ E(X)\mid U_q(X)\right] \) as follows:

$$\begin{aligned}&\Pr \left[ E(X)\mid U_q(X)\right] ~=~ \sum _{r\in X^-}\Pr \left[ E(X)\mid U_q(X), W_r(X)\right] \cdot \Pr \left[ W_r(X)\right] \\&\quad =~ \sum _{r\in X^-}\Pr \left[ E(X)\mid U_q(X), W_r(X)\right] \cdot \left( \pi (r) \cdot \prod _{p\in X^-:y(p)>y(r)}(1-\pi (p))\right) . \end{aligned}$$

There are now three cases according to the relative positions of q and r.

Case 1: \(x(r)<0<x(q)\). Let \(Y_{q,r}\subset X\) contain the points \(p\in X\) (including q) such that \(x(r)<x(p)\le x(q)\) and either \(y(p)<y(r)\) or \(y(p)\ge y(q)\). If \(r\in R\), then \(\Pr \left[ E(X)\mid U_q(X), W_r(X)\right] =1\). Otherwise, if \(r\in B\), given that \(U_q(X)\) and \(W_r(X)\) hold, any box \(D(p',q')\) defined by two red points \(p',q'\) of \(S\cap X\), containing the origin o and no other red point in \(S\cap X\), where one between \(p'\) and \(q'\) is not in \(Y_{q,r}\), will contain q or r in the interior. Then

$$\begin{aligned} \Pr \left[ E(X)\mid U_q(X),W_r(X)\right] ~=~ \Pr [E(Y_{q,r})\mid U_q(Y_{q,r})]. \end{aligned}$$

Similar arguments are given in the next two cases.

Case 2: \(0<x(q)<x(r)\). We have

$$\begin{aligned} \Pr \left[ E(X)\mid U_q(X),W_r(X)\right] ~=~ \Pr [E(X_q\cup \{q\})\mid U_q(X_q\cup \{q\})]. \end{aligned}$$

Case 3: \(0<x(r)<x(q)\). If \(r\in R\), then

$$\begin{aligned} \Pr \left[ E(X)\mid U_q(X),W_r(X)\right] ~=~ \Pr [E(Z_{q,r}\cup \{r\})\mid W_r(Z_{q,r}\cup \{r\})], \end{aligned}$$

where \(Z_{q,r}\subset X\) contains the points \(p\in X\) such that \(x(p)<x(r)\) and either \(y(p)<y(r)\) or \(y(p)>y(q)\). Note that the event \([E(Z_{q,r}\cup \{r\})\mid W_r(Z_{q,r}\cup \{r\})]\) is symmetric to the event \([E(X)\mid U_q(X)]\), thus its probability can be computed similarly. Otherwise, if \(r\in B\), we have

$$\begin{aligned} \Pr \left[ E(X)\mid U_q(X),W_r(X)\right] ~=~ \Pr [E(Z_{q,r})]. \end{aligned}$$

Note that in the above recursive computation of \(\Pr [E(X)]\), for \(X=R\cup B\), there is a polynomial number of subsets \(X_q\), \(Y_{q,r}\), and \(Z_{q,r}\); each of such subsets can be encoded in constant space (i.e., by using a constant number of coordinates). Then, we can use dynamic programming, with a polynomial-size table, to compute \(\Pr [E(R\cap B)]\) in time polynomial in n. \(\square \)

4 Discussion and Open Problems

For fixed \(d\ge 1\), the maximum box problem for non-probabilistic points can be solved in \(O(n^d)\) time [3]. This fact, combined with the Monte Carlo method and known techniques, can be used to approximate the expectation of the total weight of the maximum box on probabilistic points, in polynomial time and with high probability of success. That is, we provide a FPRAS, which is explained in Appendix C. Approximating the probability that the total weight of a maximum box is at least a given parameter is an open question of this paper. To this end, we give in Appendix D a FPRAS for approximating this probability, but only in the case where the points are colored red or blue, each with probability 1/2, and we look for the box covering the maximum number of red points and no blue point (i.e. red points have weight \(+1\) and blue points weight \(-\infty \)).

For \(d=2\) and red and blue points, there are several open problems: For example, to compute \(\Pr [\mathsf {box}(S)\ge k]\) (even for \(k=3\)) in \(d=2\) when the box is restricted to contain a fixed point. Other open questions are the cases in which the box is restricted to contain a given point as vertex, or has some side contained in a given axis-parallel line. This two latter variants can be solved in \(n^{O(k)}\) time (see Appendix E), which means that they are polynomial-time solvable for fixed k. This contrasts with the original question that is #P-hard for every \(k\ge 2\).

For red and blue points in \(d=1\), both \(\Pr [\mathsf {box}(S)\ge k]\) and \({\mathbb {E}}[\mathsf {box}(S)]\) can be computed in polynomial time by using standard dynamic programming techniques. This implies that for \(d=2\) and a fixed direction, computing the probability that there exists a strip (i.e., the space between two parallel lines) perpendicular to that direction and covering at least k red points and no blue point can be done in polynomial time. If the orientation of the strip is not restricted, then such a computation is #P-hard for every \(k\ge 3\) (see Appendix F).