Sparse Bounded Hop-Spanners for Geometric Intersection Graphs

We consider the more general setting, where $|U|=m$ and $|V|=n$. Let $T_{\mathrm{\ell }}(m,n)$ denote the worst-case optimal size of a 3-hop spanner.

Let $r$ be a parameter. By Corollary 2.5⁴⁴4For $D\le 4$, we may alternatively use traditional $(1/r)$-cuttings [2, 18, 34] (in fact, later in Theorem 2.9, we will switch back to using cuttings), but for $D\ge 5$, optimal bounds on vertical decompositions are open and polynomial partitioning gives better results. , we can partition ${ℝ}^D$ into $O(r^D)$ cells such that each cell contains at most $m/r^D$ points of $\{p_{\mathrm{\ell }}(u):u\in U\}$, and each semi-algebraic set $S_{\mathrm{\ell }}(v)$ crosses $O(r^{D-1})$ cells. For each cell $\mathrm{\Delta }$, let $U_{\mathrm{\Delta }}=\{u\in U:p_{\mathrm{\ell }}(u)\in \mathrm{\Delta }\}$, $V_{\mathrm{\Delta }}=\{v\in V:\partial S_{\mathrm{\ell }}(v)\text{crosses}\mathrm{\Delta }\}$, $V_{\mathrm{\Delta }}^{\prime }=\{v\in V:S_{\mathrm{\ell }}(v)\text{contains}\mathrm{\Delta }\}$, and $V_{\mathrm{\Delta }}^{\prime \prime }=\{v\in V:S_{\mathrm{\ell }}(v)\text{does not intersect}\mathrm{\Delta }\}$. Arbitrarily partition $V_{\mathrm{\Delta }}$ into $\lceil \frac{|V_{\mathrm{\Delta }}|}{n/r}\rceil$ subsets $V_{\mathrm{\Delta }}^{(j)}$ of size at most $n/r$ each, and recursively construct a 3-hop spanner for $G_{\mathrm{\Phi }}[U_{\mathrm{\Delta }},V_{\mathrm{\Delta }}^{(i)}]$ for each $V_{\mathrm{\Delta }}^{(i)}$. Since ${\sum }_{\mathrm{\Delta }}|V_{\mathrm{\Delta }}|=O(n{r}^{D-1})$, the number of such recursive calls is $O(r^D)$. Furthermore, for each cell $\mathrm{\Delta }$, recursively construct a 3-hop spanner for $G_{{\mathrm{\Phi }}^{\prime }}[U_{\mathrm{\Delta }},V_{\mathrm{\Delta }}^{\prime }]$ and a 3-hop spanner for $G_{{\mathrm{\Phi }}^{\prime \prime }}[U_{\mathrm{\Delta }},V_{\mathrm{\Delta }}^{\prime \prime }]$, where ${\mathrm{\Phi }}^{\prime }$ (resp., ${\mathrm{\Phi }}^{\prime \prime }$) is the $(\mathrm{\ell }-1)$-variate Boolean formula obtained by setting the $\mathrm{\ell }$-th variable to true (resp., false). The union of these spanners yields a 3-hop spanner for $G_{\mathrm{\Phi }}[U,V]$. We thus obtain the following recurrence for $\mathrm{\ell }\ge 1$:

For base cases, we have $T_0(m,n)=O(m+n)$ (since a biclique $U\times V$ has a 3-hop spanner of linear size, consisting of two stars, centered at a fixed vertex of $U$ and a fixed vertex of $V$), and we can use the upper bound $T_{\mathrm{\ell }}(m,n)\le O(m^2+n)$ for every $\mathrm{\ell }$ by Lemma 2.1.

Assume inductively that $T_{\mathrm{\ell }-1}(m,n)=O^{\ast }(m^{\frac{2D-2}{2D-1}}{n}^{\frac{D}{2D-1}})$ for $\sqrt{n}\le m\le n^D$. Choose $r$ to be a large constant. Expand the recurrence for $k$ levels so that ${(m/r^{Dk})}^2\approx n/r^k$, i.e., $r^k\approx {(m^2/n)}^{\frac{1}{2D-1}}$. Then the recurrence (1) yields

Making $r$ an arbitrarily large constant, this yields $T_{\mathrm{\ell }}(m,n)=O^{\ast }(m^{\frac{2D-2}{2D-1}}{n}^{\frac{D}{2D-1}})$ for $\sqrt{n}\le m\le n^D$. $◀$

Theorem 2.7 immediately implies an $o(n^{3/2})$ bounds on 3-hop spanners for intersection graphs of any family of objects with constant description complexity.

Polyhedra of constant complexity can be decomposed into $O(1)$ simplices. A simplex in ${ℝ}^d$ has $d+1$ vertices, so it can be encoded as a point in ${ℝ}^{d(d+1)}$, and the set of all simplices intersecting a given simplex maps to a semi-algebraic set in ${ℝ}^{d(d+1)}$. We can thus apply Theorem 2.7 with $D=d^2+d$.

We can decrease $D$ with more care. For example, for $d=3$, two simplices $s$ and $s^{\prime }$ intersect if and only if (a) a vertex of $s$ is inside $s^{\prime }$, or (b) an edge $pq$ of $s$ intersects a facet $\tau$ of $s^{\prime }$, or vice versa. The toughest case concerns (b), which is equivalent to: (i) the line through $pq$ intersects $\tau$, and (ii) $p$ lies above the plane through $\tau$, and (iii) $q$ lies below the plane through $\tau$, or vice versa. In (i), the line through $pq$ can be encoded as a point in ${ℝ}^4$, whereas in (ii) or (iii), $p$ or $q$ is already a point in ${ℝ}^3$. We can thus apply Theorem 2.7 with $D=4$ (rather than $d(d+1)=12$). $◀$

A red ball with center $(x_1,\mathrm{\dots },x_d)$ and radius $y$ intersects a blue ball with center $(a_1,\mathrm{\dots },a_d)$ and radius $b$ iff ${(x_1-a_1)}^2+\mathrm{\cdots }+{(x_d-a_d)}^2\le {(y+b)}^2$, i.e., the point $(x_1,\mathrm{\dots },x_d,y,x_1^2+\mathrm{\cdots }+x_d^2-y^2)\in {ℝ}^{d+2}$ lies inside the halfspace $\{(x_1,\mathrm{\dots },x_d,y,z)\in {ℝ}^{d+2}:z-2a_1{x}_1-\mathrm{\cdots }-2a_d{x}_d-2by+a_1^2+\mathrm{\cdots }+a_d^2-b^2\le 0\}$. Thus, we can apply Theorem 2.9 with $D=d+2$. $◀$

Note that in the non-bipartite case, an $O(n\log n)$ bound is known for 3-hop spanners [16], by exploiting the fatness of balls. In the next section, we show that the bound in Corollary 2.10 actually holds for 2-hop spanners for balls in the non-bipartite setting.

We construct a spanner subgraph $H^{+}$ of $G^{+}$ as follows. For each vertex $v\in V$, $\mathrm{deg}(v)\ge 1$, let $e_v$ be an arbitrary edge incident to $v$, and add $e_v$ to $H^{+}$. Furthermore, add the clique on $U$ to $H^{+}$. We show that $H^{+}$ is a 2-hop spanner of $G^{+}$. Consider an edge $uv$ in $G$. If $e_v=uv$, then we can go from $u$ to $v$ in 1 hop. Otherwise, say $e_v$ is $u^{\prime }v$. We can go from $u$ to $v$ in 2 hops via the edges $u{u}^{\prime }$ and $u^{\prime }v$. $◀$

The above lemma implies an $O(n^{3/2})$ upper bound on 2-hop spanners in this setting, by the same grouping trick from the proof of Corollary 2.2:

We also immediately obtain the following analogs to Theorems 2.7 and 2.9:

We follow the proof of Theorem 2.7, but using Lemma 3.1 in place of Lemma 2.1. We also add a 2-hop spanner for $U\times U$ of $O(m)$ size (namely, a star). $◀$

We follow the proof of Theorem 2.7, but using Lemma 3.1 in place of Lemma 2.1, and just replacing the path ${\pi }_{p,p^{\prime }}$ with an edge $p{p}^{\prime }$. $◀$

Recall that a quadtree cell is an axis-aligned box of the form $[i_1/2^k,(i_1+1)/2^k)\times \mathrm{\cdots }\times [i_d/2^k,(i_d+1)/2^k)$ for some integers $i_1,\mathrm{\dots },i_d,k$. An object $u$ of diameter $\mathrm{\ell }$ is $C$-aligned if it is contained in a quadtree cell of side length $C\mathrm{\ell }$. As argued in [16, Section 3.1], as a consequence of a known shifting lemma [13], one can find $O(d)$ vectors ${\tau }_1,\mathrm{\dots },{\tau }_{O(d)}$ with the property that for every pair of objects $u$ and $v$, there exists at least one vector ${\tau }_j$ such that $u+{\tau }_j$ and $v+{\tau }_j$ are both $C$-aligned for some $C=O(d)$. For each ${\tau }_j$, it suffices to construct a 2-hop spanner for the subset of all objects $u$ such that $u+{\tau }_j$ is $C$-aligned; we can then output the union of these $O(d)$ spanners. From now on, we may thus assume that all objects are $C$-aligned. Let $T(n)$ be the worst-case optimal 2-hop spanner size under this assumption.

1. 1.

   First find a quadtree cell $\gamma$ such that there are at most $\alpha n$ objects completely inside $\gamma$ and at most $\alpha n$ objects completely outside $\gamma$, with $\alpha :=\frac{2^d}{2^d+1}$; see [16, Lemma 10] (based on earlier work in [5, 12]). This cell corresponds to a “centroid” of the quadtree. Recursively construct a 2-hop spanner for the objects completely inside $\gamma$ and a 2-hop spanner for the objects completely outside $\gamma$.

2. 2.

   Let $Q_{\gamma }$ be a set of points hitting all objects that intersect $\partial \gamma$. By alignedness, these objects have diameter at least ${\mathrm{\ell }}_{\gamma }/C$, where ${\mathrm{\ell }}_{\gamma }$ denotes the side length of $\gamma$. By fatness, a hitting set of size $|Q_{\gamma }|=O(1)$ exists (since $\partial \gamma$ can be covered by $C^d$ hypercubes of side length ${\mathrm{\ell }}_{\gamma }/C$).

3. 3.

   For each point $q\in Q_{\gamma }$, let $U_q$ be the subset of all objects hit by $q$ (this subset induces a clique). Let $G_q$ be the bipartite intersection graph between $U_q$ and $V$. Construct a 2-hop spanner for $G_q\cup (U_q\times U_q)$ by Corollary 3.2.

We claim that the union of the spanners found is a 2-hop spanner of $G$. To see this, consider an edge $uv$ in $G$. If $u$ and $v$ are both inside $\gamma$ or both outside $\gamma$, then $u$ and $v$ are reachable by 2 hops by induction. Otherwise, one of the objects, say $u$, intersects $\partial \gamma$. Then $u$ is hit by some point $q\in Q_{\gamma }$, and so $uv\in G_q$ and $u$ and $v$ are reachable by 2 hops.

We thus obtain the following recurrence:

This solves to $T(n)=O(n^{3/2})$. $◀$

We similarly obtain improvements when the fat objects are semialgebraic with constant description complexity:

Same as the proof of Theorem 3.5, but using Theorem 3.3 instead of Corollary 3.2. $◀$

As in the proof of Corollary 2.8, this follows by setting $D=d^2$, or in the $d=3$ case, $D=4$. $◀$

Same as the proof of Theorem 3.5, but using Theorem 3.4 instead of Corollary 3.2. $◀$

As in the proof of Corollary 2.10, this follows from Theorem 3.8 by setting $D=d+2$. $◀$

For fat axis-aligned boxes, we have the following theorem, which generalizes a result by Conroy and Tóth [20] from $d=2$ to higher dimensions:

Same as the proof of Theorem 3.6, but to construct a 2-hop spanner for $G_p\cup (U_q\times U_q)$, we use a known biclique cover construction for the bipartite intersection graph $G_p$ of boxes: this gives a collection of bicliques of the form $U_i\times V_i$, covering all the edges of $G_p$, with total size ${\sum }_i(|U_i|+|V_i|)=O(n{\log }^{d}n)$. (The construction is obtained by range-tree-style divide-and-conquer; e.g., see [14].) When the clique $U_i\times U_i$ is added to the biclique $U_i\times V_i$, there is a trivial 2-hop spanner of size $O(|U_i|+|V_i|)$ (namely, take a star centered at an arbitrary point in $U_i$). We just take the union of these spanners (together with a linear-size 2-hop spanner for $U_q\times U_q$) and obtain a spanner of size $O(n{\log }^{d}n)$ for $G_p\cup (U_q\times U_q)$. The recursion in the proof of Theorem 3.6 causes one more logarithmic factor. $◀$

We note that the known $O(n\log n)$-size 3-hop spanner construction for axis-aligned rectangles in ${ℝ}^2$ by Chan and Huang [16] can be extended to give an $O(n{\log }^{d-1}n)$-size 3-hop spanner for axis-aligned boxes in ${ℝ}^d$. We defer this result to arXiv [9].