Approximating Klee’s Measure Problem and a Lower Bound for Union Volume Estimation

A major application of union volume estimation is DNF counting, in which we are given a Boolean formula in disjunctive normal form and want to count the number of satisfying assignments. Computing the exact number of satisfying assignments is #P-complete, so it likely requires superpolynomial time. Approximating the number of satisfying assignments can be achieved by a direct application of union volume estimation, as described in [19]. Their algorithm remains the state of the art for approximate DNF counting, see e.g. [24]. This has been extended to more general model counting [27, 9, 24], probabilistic databases [20, 15, 28], and probabilistic queries on databases [7].

We also mention network reliability as another application for union volume estimation, which was already discussed in [19]. Additionally, Karger’s famous paper on the problem [17] uses the algorithm of [19] as a subroutine. However, the current state-of-the-art algorithms no longer use union volume estimation as a tool [8].

Finally, we want to draw a connection to the following well-known query sampling bound. Canetti, Even, and Goldreich [6] showed that approximating the mean of a random variable whose codomain is the unit interval requires $\mathrm{\Omega }(1/{\epsilon }^2)$ queries, thus obtaining tight bounds for the sampling complexity of the mean estimation problem. Their bound generalize to $\mathrm{\Omega }(1/(\mu {\epsilon }^2))$ on the number of queries needed to estimate the mean $\mu$ of a random variable in general. Before our work it was thus natural to expect that the $1/{\epsilon }^2$ dependence in the number of queries for union volume estimation is optimal. However, whether the factor $n$ is necessary, or the number of queries could be improved to, say, $O(n+1/{\epsilon }^2)$, was open to the best of our knowledge.

Klee’s measure problem is an important problem in computational geometry. One reason for its significance is that techniques developed for it can often be adapted to solve various related problems, such as the depth problem (given a set of boxes, what is the largest number of boxes that can be stabbed by a single point?) [13] or Hausdorff distance under translation in $L_{\mathrm{\infty }}$ [14]. Moreover, various other problems can be reduced to Klee’s measure problem or to its related problems. For example, deciding whether a set of boxes covers its boundary box can be reduced to Klee’s measure problem [13]. The continuous $k$-center problem on graphs (i.e., finding centers that can lie on the edges of a graph that cover the vertices of a graph) is reducible to Klee’s measure problem as well [29]. Finding the smallest hypercube containing at least $k$ points among $n$ given points can be reduced to the depth problem [16, 10, 13]. In light of this, it would be interesting to see if our approximation techniques generalize to any of these related problems.

Due to our lower bound, we have to exploit the structure of the input boxes to obtain a running time of the form $O\left((n+\frac{1}{{\epsilon }^2})\cdot \mathrm{polylog}(n)\right)$. We follow the common algorithmic approach of sampling. Specifically, we aim to sample a set $S$ from the union of boxes such that each point is selected with probability density $p$. For appropriately defined $p$, the value $|S|/p$ is a good estimate of the volume of the union. In the overview we assume that a proper $p$ is given and focus on the main difficulty: creating a sample set $S$ for the given $p$.

We start by sorting the input boxes into classes by shape. Two boxes are in the same class if, in each dimension $k\in [d]$, their side lengths are both in $[2^{L_k},2^{L_k+1})$ for some $L_k\in \mathbb{Z}$. We call two classes similar if the corresponding side lengths are polynomially related (e.g., within a factor of $n^4$) in each dimension. We make two crucial observations:

1. 1.

   Each class is similar to only polylogarithmically many classes (Observation 11).

2. 2.

   Dissimilar classes have a small intersection compared to their union (Observation 12, Figure 1).

Our algorithm continues as follows. We scan through the classes in an arbitrary order. For each class, we sample with density $p$ from the union of the boxes in this class, but we only keep a point if it is not contained in any class that comes later in the order. To efficiently test containment in a later class, we use an orthogonal range searching data structure (with an additional dimension for the index of the class). When the scan finishes, we obtain a desired sample set $S$.

Let us elaborate why the algorithm is efficient.

Sampling from a single class.

Our approach is simple yet powerful: (i) grid the space into cells of side lengths comparable to the boxes in this class; (ii) sample points from the relevant cells uniformly at random; (iii) discard points outside the union by querying an orthogonal range searching data structure. See Figure 2. All these steps exploit the geometry of boxes. Since the grid cells and boxes have roughly the same shape, a significant fraction of the points sampled in (ii) are contained in the union, i.e., not discarded in (iii). The orthogonal range searching data structure allows us to quickly decide which points to discard. These explain the efficiency of sampling from a class.

Bounding the amount of wasted work.

Sampled points that appear in later classes also need to be discarded, and this is a potential (and only) source of inefficiency. So we need to bound the number of them. Such a point shows up later either (i) in a similar class, or (ii) in a dissimilar class. Our first observation stated that a class is similar to at most polylogarithmically many classes. So (i) can happen up to polylogarithmically many times from the perspective of a fixed point in the union. On the other hand, our second observation stated that the intersection of dissimilar classes is small. So on average (ii) rarely happens and does not affect the expected running time significantly.

Our lower bound is shown by a reduction from the Query-Gap-Hamming problem: Given two vectors $x,y\in {\{-1,+1\}}^{\mathrm{\ell }}$, distinguish whether their inner product is greater than $\sqrt{\mathrm{\ell }}$ or less than $-\sqrt{\mathrm{\ell }}$. It is known that any algorithm distinguishing these two cases with success probability at least $2/3$ must access $\mathrm{\Omega }(\mathrm{\ell })$ bits of $x$ and $y$.

We first sketch why $\mathrm{\Omega }(1/{\epsilon }^2)$ queries are necessary to $(1+\epsilon )$-approximate the volume of the union of two objects in the query model. Given a Query-Gap-Hamming instance $x,y$, we construct two objects $X=\{(j,x_j):j\in [\mathrm{\ell }]\}$ and $Y=\{(j,y_j):j\in [\mathrm{\ell }]\}$. These are discrete point sets, but they can be inflated to polygons such that cardinality corresponds to volume. See Figure 3 for an example. Note that for all $k\in \{0,\mathrm{\dots },\mathrm{\ell }\}$, we have

If an algorithm $𝒜$ can $(1+\epsilon )$-approximate $|X\cup Y|$, then it can approximate $k$ within additive error $2\epsilon \mathrm{\ell }$, thus it can also approximate $⟨x,y⟩$ within additive error $4\epsilon \mathrm{\ell }$. Setting $\mathrm{\ell }=1/(16{\epsilon }^2)$, the additive error is at most $4\epsilon \mathrm{\ell }=4\cdot \frac{1}{4\sqrt{\mathrm{\ell }}}\cdot \mathrm{\ell }=\sqrt{\mathrm{\ell }}$, which suffices to distinguish $⟨x,y⟩=\sqrt{\mathrm{\ell }}$ from $⟨x,y⟩=-\sqrt{\mathrm{\ell }}$ and thereby solves the Query-Gap-Hamming instance.

Note that $|X|=|Y|=\mathrm{\ell }$, so a volume query does not disclose any information about $x$ and $y$. Each sample or containment query accesses at most one bit of $x$ or $y$. Therefore, algorithm $𝒜$ has to make $\mathrm{\Omega }(\mathrm{\ell })=\mathrm{\Omega }(1/{\epsilon }^2)$ queries to $X,Y$.

In order to generalize this lower bound for the union of two objects to an $\mathrm{\Omega }(n/{\epsilon }^2)$ lower bound for the union of $n$ objects, we need to ensure that each query gives away only $O(1/n)$ bits of information about $x$ and $y$. We apply two obfuscations that jointly slow down the exposure of bits; see Figure 4. Firstly, we introduce objects $X_1,\mathrm{\dots },X_n$ whose union is $X$ and objects $Y_1,\mathrm{\dots },Y_n$ whose union is $Y$. Imagine cutting each $X$-induced rectangle in Figure 3 into $n$ side-by-side pieces and distributing them randomly among $X_1,\mathrm{\dots },X_n$. Do the same for $Y$. The idea is that one needs to make $\mathrm{\Omega }(n)$ containment queries on the rectangular region in order to hit the correct piece; only then is the corresponding bit revealed. Secondly, we introduce a large band shared by all $X_i$ and $Y_i$ for $i\in [n]$. In Figure 4, this is the long dark-blue rectangle that spans from left to right. Intuitively it enforces $\mathrm{\Omega }(n)$ sample queries to obtain a single point that contains any information about $x$ and $y$.

In Klee’s measure problem we are given boxes $O_1,\mathrm{\dots },O_n\subset {ℝ}^d$. Here, a box is an object of the form $O_i=[a_1,b_1]\times \mathrm{\dots }\times [a_d,b_d]$, and as input we are given the coordinates $a_1,b_1,\mathrm{\dots },a_d,b_d$ of each box. Based on these, it is easy to compute the side lengths and volume of each box.

Throughout we write $V:=\mathrm{Volume}({\bigcup }_{i=1}^n{O}_i)$ for the volume of the union of boxes. The goal is to approximate $V$ up to a factor of $1+\epsilon$. Our approach is based on sampling, so now let us introduce the relevant notions.

Recall the Poisson distribution $\mathrm{Pois}(\lambda )$ with mean and variance $\lambda$: It captures the number of active points in a universe, under the assumption that active points occur uniformly and independently at random across the universe, and that $\lambda$ points are active on average. The following definition is usually referred to as a homogeneous Poisson point process at rate $p$. Intuitively, we activate each point in some universe $U\subset {ℝ}^d$ independently with “probability density” $p$, thus the number of activated points follows the Poisson distribution with mean $p\cdot \mathrm{Volume}(U)$.

In particular, if $S$ is a $p$-sample of $U$, then $|S|\sim \mathrm{Pois}(p\cdot \mathrm{Volume}(U))$. Two more useful properties follow from the definition:

1. (i)

   For any measurable subset $U^{\prime }\subseteq U$, the restriction $S\cap U^{\prime }$ is a $p$-sample of $U^{\prime }$.

2. (ii)

   The union of $p$-samples of two disjoint sets $U,U^{\prime }$ is a $p$-sample of $U\cup U^{\prime }$.

Besides sampling, we will apply orthogonal range searching to handle the so-called $\text{appears}(x,i)$ query: Given $x\in {ℝ}^d$ and $i\in \mathbb{N}$, is $x\in O_i\cup \mathrm{\cdots }\cup O_n$?

For our algorithm to work, we also need a constant-factor approximation of the volume $V$. It is known that this can be computed in $O(n)$ time [19]. In order to stay simple and self-contained, we state a weaker result by implementing the Karp-Luby algorithm [18] with the help of appears queries.

As our first step in the algorithm, we classify boxes by their shapes.

Using this definition, we partition the input boxes $O_1,\mathrm{\dots },O_n$ into classes $C_1,\mathrm{\dots },C_m$ such that each class corresponds to one type of boxes. The notation is fixed from now on. For each $t\in [m]$, we denote $U_t:={\bigcup }_{O\in C_t}O\subset {ℝ}^d$, namely the union of boxes in class $C_t$.

Similar to appears, we may use orthogonal range searching to handle the so-called $\text{inClass}(x,t)$ query: Is a given point $x\in {ℝ}^d$ contained in $U_t$?

Recall that $C_1,\mathrm{\dots },C_m$ are the classes of the input boxes and $U_1,\mathrm{\dots },U_m$ their respective unions. Assume without loss of generality that the boxes are ordered in accordance with the class ordering, that is, $C_1=\{O_1,\mathrm{\cdots },O_{i_1}\}$ form the first class, $C_2=\{O_{i_1+1},\mathrm{\cdots },O_{i_2}\}$ form the second class, and so on. In general, we assume that $C_t=\{O_{i_{t-1}+1},\mathrm{\dots },O_{i_t}\}$ for all $t\in [m]$, where .

Let $D_t:=U_t\setminus ({\bigcup }_{s=t+1}^m{U}_s)$ be the points in $U_t$ that are not contained in later classes. Note that $D_1,\mathrm{\dots },D_m$ is a partition of ${\bigcup }_{t=1}^m{U}_t={\bigcup }_{i=1}^n{O}_i$. Hence, to generate a $p$-sample of ${\bigcup }_{i=1}^n{O}_i$, it suffices to draw $p$-samples from each $D_t$ and then take their union.⁴⁴4This idea has previously been used on objects, by considering the difference $D_i^{\prime }:=O_i\setminus ({\bigcup }_{j=i+1}^n{O}_j)$ [18, 25], while we use this idea on classes. To this end, we draw a $p$-sample $S_t$ from $U_t$ via Lemma 8. Then we remove all $x\in S_t$ for which $\text{appears}(x,i_t+1)=\text{true}$; these are exactly the points that appear in a later class. What remains is a $p$-sample of $D_t$. The union of these sets thus is a $p$-sample of ${\bigcup }_{i=1}^n{O}_i$, and we can use the size of this $p$-sample to estimate the volume $V$ of ${\bigcup }_{i=1}^n{O}_i$. The complete algorithm is summarized in Algorithm 1.