Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds

In this subsection, we very briefly outline some key aspects of prior work. A significantly extended form of this section is in the appendix of the full version.

Most importantly for our methods, Kumar, Lokshtanov, Saurabh and Suri [13, Section 6] describe an algorithm that runs in polynomial time in the arrangement model. Their algorithm implicitly makes use of the homology cover (perhaps unintentionally), in the same sense that we will use it. In fact, their algorithm is in some ways analogous to an algorithm of Chambers, Erickson, Fox, and Nayyeri [5] for minimum-cuts (and maximum-flow) in surface graphs. These two algorithms are the main inspiration for our approach to the $(s,t)$ point-separation at a high-level, in all models.

We obtain improved algorithms for the $(s,t)$-point separation problem in several cases, which we outline in Table 1. As mentioned earlier, all of our positive results make use of a reduction to a shortest-path problem in the so-called “homology cover”. We discuss this formulation in Section 2, and then again more rigorously in the appendix of the full version. Using this reduction, the upper bounds are then given in Section 3.

We also obtain several fine-grained lower bounds in Section 4. Our lower bounds also all have a shared foundation, which will be stated in Theorem 13. The resulting lower bounds are based on a few different hypotheses, and we give their details in the appendix of the full version.

We now have tools for characterizing closed curves that separate $s$ and $t$. We’d now like to characterize sets of obstacles that separate $s$ and $t$. In other words, we’d like to characterize unions of closed curves (obstacles) that contain a closed curve separating $s$ and $t$. We’ll give two different tools for this, first for the arrangement model, then for the oracle model. For simplicity, we will work exclusively with obstacles that do not individually separate $s$ and $t$ (that is, obstacles that get mapped to two separate closed curves in the homology cover). We will reduce to this case algorithmically at the start of Section 3.

In the arrangement model of the $(s,t)$ point-separation problem, we are given a plane graph $D$ (the arrangement) with specified faces $s$ and $t$ (can be obtained from points via point-location), and a set of obstacles $\sigma$, each given as a connected subgraph. The homology cover has a simple graph-theoretic interpretation in this framework: Take any (simple) dual-path $\pi$ of faces from $s$ to $t$ – this is will serve as the “portal”. Next, create two copies $D_1,D_2$ of $D$, each with the faces $s$ and $t$ removed. We will create a combined graph $\overline{D}$ starting from the union of $D_1$ and $D_2$. For each edge $e=uv$ used in the dual-path $\pi$, delete $e$ from both $D_1$ and $D_2$ (inside $\overline{D}$). Denote the corresponding vertices of $u$ and $v$ in each of $D_1$ and $D_2$ as $u_1,v_1$ and $u_2,v_2$, respectively. Then create new edges $u_1{v}_2$ and $u_2{v}_1$ in $\overline{D}$. This form of the homology cover is visualized in Figure 9.

With this particular arrangement structure Kumar, Lokshtanov, Saurabh and Suri [13, Section 6] built a graph using one vertex per obstacle-vertex incidence (in each copy of the plane graph). We will build a smaller graph of similar form to theirs. First, for each obstacle $C\in \sigma$ (which induces a subgraph of $D$), pick some arbitrary canonical point $x\in C$. Since this choice is arbitrary, it will sometimes be useful to assume it is a specific point – this will primarily be useful for specific obstacle types. Assume that $x$ is also a vertex in the subgraph of $D$ induced by $C$ (and if it is not, modify $D$ so that it is, with either a subdivision or a new degree-$1$ vertex). Note that since $C$ is connected in $D$, every other vertex $x^{\prime }\in C$ is connected to $x$ by only edges in $C$. Given a plane graph $D$ with faces $s$ and $t$, a dual-path $\pi$, obstacles $\sigma$, and canonical points for each obstacle, the auxiliary graph $H$ is a bipartite graph constructed as follows:

• $\mathrm{■}$

  The first set of vertices are the copies of arrangement vertices in the homology cover. For a vertex $v\in V(D)$, we denote these two copies $v^{+}$ and $v^{-}$.

• $\mathrm{■}$

  The second set of vertices are the copies of the obstacles/canonical points in the homology cover. For an obstacle $\gamma \in \sigma$, we denote these two copies as $(\gamma ,-)$ and $(\gamma ,+)$.

• $\mathrm{■}$

  The values $-$ and $+$ in each of the above are indicator bits, and can be stored as $0$ and $1$, respectively.

• $\mathrm{■}$

  A vertex copy $v^{b_1}$ has an edge connecting it to a canonical point copy $(\gamma ,b_2)$ when:

  • –

    $v\in \gamma$ (that is, the point $v$ belongs to the obstacle $\gamma$ in the arrangement), and…

  • –

    The canonical point $x$ of $\gamma$ has a path through the edges of $\gamma$ to $v$ whose intersection with the edges of $\pi$ has size $b_1+b_2$ modulo $2$ (i.e., if $b_1=b_2$, the size must be even, and if $b_1\ne b_2$, the size must be odd). Equivalently, the projected connected component of $\gamma$ containing the canonical point copy $(\gamma ,b_2)$ also contains $v^{b_1}$.

We visualize an example of the auxiliary graph in Figure 10.

The auxiliary graph is useful because the shortest path between any two corresponding vertex copies or (separately) any two corresponding canonical point copies both correspond exactly to the solution to the $(s,t)$ point-separation problem. The high-level construction to prove this fact is as follows:

• $\mathrm{■}$

  Suppose there is a set of obstacles $C$. We’d like to determine when $C$ separates $s$ and $t$.

• $\mathrm{■}$

  Denote the set of copies of the obstacles in $C$ in the homology cover as $C^{\prime }$, so that every element of $C^{\prime }$ is a closed curve representing one of the two connected components of an element of $C$ projected into the homology cover.

• $\mathrm{■}$

  By Fact 1, we deduce that $C$ separates $s$ and $t$ if and only if there is a path from $v^{+}$ to $v^{-}$ along the union of obstacle copies in $C^{\prime }$, for some arrangement vertex $v$ among pairs of elements in $C$ only.

• $\mathrm{■}$

  Moreover, since each obstacle is connected, we may further assume that any such path visits each obstacle copy at most once, and moreover that it only visits each obstacle at most once.

• $\mathrm{■}$

  We may further assume that any such path visits the canonical point copy of each such obstacle copy, by inserting a path to and then from the canonical point copy while the obstacle copy is visited. Note that the resulting path may not be simple in the plane.

• $\mathrm{■}$

  Such paths also directly correspond to paths in the auxiliary graph, using only “obstacle vertices” corresponding to elements of $C$ and the “arrangement vertices” incident to pairs of elements in $C$.

• $\mathrm{■}$

  With appropriate weights, the problem of finding the minimum-weight set $C$ with this property then reduces to the problem of finding the pair $v^{+},v^{-}$ with the shortest distance in the auxiliary graph, so this is a shortest-path problem!

• $\mathrm{■}$

  A similar argument can show that an alternative algorithmic formulation is to find the pair $(\gamma ,-),(\gamma ,+)$ with the shortest-distance in the auxiliary graph.

This essentially completes the set of tools necessary for the arrangement model. These arguments are given in more detail in the appendix of the full version.

For the oracle model, the purpose of the oracles will be to construct the geometric intersection graph of the obstacle copies in the homology cover (which we will denote as $\overline{G}$). We will call $\overline{G}$ the intersection graph in the homology cover. See Figure 11 for an example. We will present two different constructions of this graph. They are equivalent, and each of them is quite simple, but they will serve two different purposes: The first will clarify which types of oracle queries are necessary, and provide an algorithmic construction. The second will instead build on the tools we have for the arrangement model, proving the correctness of another shortest-paths approach.

Let $𝒞$ denote the set of obstacles in the plane. We assume the canonical points for each obstacle are given (or implied) – they will be used by the oracle. We also assume some simple $s-t$ path $\pi$ is fixed – this will also be used by the oracle. In most cases, $\pi$ will be $\overline{st}$. The first construction of the graph is as follows:

• $\mathrm{■}$

  For each obstacle $\gamma \in 𝒞$, create two vertices $(\gamma ,-)$ and $(\gamma ,+)$.

• $\mathrm{■}$

  For each pair of obstacles ${\gamma }_1,{\gamma }_2$ with canonical points $x_1,x_2$, and values $b_1,b_2\in \{-,+\}$, we connect vertices $({\gamma }_1,b_1)$ and $({\gamma }_2,b_2)$ by an edge if there is a path from $x_1$ to $x_2$ in ${\gamma }_1\cup {\gamma }_2$ crossing $\pi$ exactly $k$ times, for some $k$ where $k\equiv b_1+b_2(mod2)$.

Testing for this condition is actually the only type of oracle query needed (although we will also require support for the case when ${\gamma }_1={\gamma }_2$ later). Cabello and Giannopoulos [3] used a larger set of query types, but together they can be used to perform this type by carefully choosing the canonical points and fixing $\pi$ to $\overline{st}$, so our variant of the oracle model is slightly more general (although practically equivalent).

We’d like a similar algorithmic property for the intersection graph in the homology cover $\overline{G}$ that we have for the auxiliary graph $H$. The second construction will be what gives us that property, by constructing $\overline{G}$ from $H$:

• $\mathrm{■}$

  For each arrangement vertex $v^b$ in $H$, let its adjacent vertices be denoted $x_1,\mathrm{\dots },x_k$. Delete $v^b$ and create a clique over $\{x_1,\mathrm{\dots },x_k\}$.

• $\mathrm{■}$

  After performing this for every arrangement vertex $v^b$, the result is exactly the intersection graph in the homology cover $\overline{G}$.

• $\mathrm{■}$

  Therefore, the set of vertices visited by the shortest path from some $(\gamma ,-)$ to $(\gamma ,+)$ (over all possible $\gamma \in 𝒞$, breaking ties arbitrarily) corresponds to a minimum-weight set of obstacles separating $s$ and $t$.

For specific obstacle types, we will usually work with $\overline{G}$, although we will do it implicitly. Hence, with the tools from this section, we can now discuss algorithms in all three model types as solutions to a certain form of shortest-path problem.

With no significant further work, we already obtain some naïve algorithms by using a result in the appendix of the full version (or the constructions in Section 2):

We are also interested in the $(s,t)$ point-separation problem for unit weights, which corresponds to shortest paths for unit weights. In this case, we can obtain faster algorithms:

We can also obtain results using the arrangement instead of the intersection graph. The simplest of these is a slight modification of Theorem 3:

As we will discuss in the appendix of the full version, Chan and Skrepetos [6, 7] studied APSP for several forms of unweighted/undirected geometric intersection graphs. Their intersection graphs are in the plane, but with some extra work it is possible to study intersection graphs in the homology cover, and consequently the unweighted $(s,t)$ point-separation problem.

We will now present a method for solving the weighted $(s,t)$ point-separation problem using a tool called “biclique covers”, which are essentially a tool for a type of graph sparsification.

For a graph $G=(V,E)$, a biclique in $G$ is a complete bipartite subgraph ($A\times B\subset E$, where $A,B\subset V$ are disjoint). The size of a biclique is the number of vertices it contains ($|A|+|B|$). A biclique cover is a collection of bicliques in $G$ covering the edges $E$, and its size is the the sum of all sizes in its bicliques. Biclique covers of geometric intersection graphs in two-dimensions are well-studied. We summarize known results in Table 2.

Biclique covers are useful in our case because they can be used for faster vertex-weighted shortest paths. In particular:

We leave the proof to the appendix of the full version.

These results aren’t quite enough for the $(s,t)$ point-separation problem, since what we need is actually a biclique cover in the homology cover. Fortunately, we can construct this:

We leave the proof of this to the appendix of the full version as well. The proof is similar to that of Theorem 7.

The combination of these results gives the following theorem:

Note that a biclique cover for $O(1)$-length polylines can be recovered from biclique covers over the individual line segments (adjusted slightly so that the line segments in the same polyline do not overlap).