Link Diameter, Radius and 2-Point Link Distance Queries in Polygonal Domains

Both geodesic (shortest) and minlink paths may be more intricate than it feels from a glance:

• $\mathrm{■}$

  It is folklore that geodesic paths may be found by searching the visibility graph of the domain; however, even if the vertices have integer coordinates, it is not known whether one can compare, in polynomial time, the length of a path to an integer – the length is the sum of square roots and no polynomial-time algorithm is known for comparing the sum to a number.

• $\mathrm{■}$

  As explained in Section 2.1, vertices of a minlink path cannot always be snapped to a discrete set of points, leading to high bit complexity of the paths even in simple polygons [19, 21]. In a polygonal domain with holes, it is not immediately clear how to find a minlink path in polynomial time. One may compute the $k$-link reachable regions, from the starting point, for increasing $k$, but bounding the complexity of the regions (and hence the algorithm’s runtime) requires an insight [25].

The problems considered in this paper (2-point shortest path queries, diameter and radius) take the complexity to the next level. Quoting [5]: “no algorithm for computing the diameter and radius under the link distance is known, not even one that runs in exponential time.” In particular, nothing directly prevents the problems from being NP-hard or $\exists ℝ$-hard. We show that the problems admit polynomial-time solutions. The running times are high: we leave the speed up as future work. (Note that there are plenty of algorithms with high running times that “just” show polynomiality of long-standing open problems; computational geometry examples range from a 20yr-old $O(n^{29}\log n)$-time approximation algorithm [13] for covering an $n$-gon with fewest convex subpolygons to a recent $O(n^{107})$-time algorithm for star-partitioning a simple polygon[1].)

Computing the link diameter and radius/center of a polygonal domain with holes has been open since analogous problems were considered for simple polygons some 30 years ago [28, 4]. The reason why even an exponential-time solution is not obvious is because vertices of a minlink path do not necessarily lie on VG or some other discrete structure determined from the polygon (Fig. 1): it was shown [19, 21] that $\mathrm{\Theta }(n\log n)$ bits may be required to represent coordinates of vertices of the minlink path, even if the vertices of $P$ have integer coordinates specified with $O(\log n)$ bits.

Algorithms for computing the link distance from a source point $s$ [26, 15, 17, 25] employ the “staged illumination” paradigm (see, e.g., the handbooks [23, Chapter 12] and [30, Chapter 31.3]): At the first stage, place the light source at $s$ and illuminate VP of $s$ – this is the set of points with link distance 1 from $s$. At the beginning of any subsequent stage, the boundary between the lit and the dark portions of $P$ is defined by a set of line segments we call windows (any window starts at a vertex and ends on the boundary of $P$) which bound the weak visibility polygon of the area lit at the previous stage.

Figure 2 (left)t illustrates the staged illumination in a simple polygon. To efficiently run the staged illumination in a polygonal domain with holes [25], some chains of windows are replaced by their relative convex hulls within $P$ – essentially snapping windows to edges of VG. See Figure 2 (right) and [25], in particular, Figures 2–5 therein for the details.

The greedy path [22, 4] from $s$ to a window $w$ is the minlink path whose links are all aligned with windows and whose last link is aligned with $w$. E.g., the path in Fig. 1 is greedy.

The link distance map, denoted LDM($s$), from the source point $s$ is a decomposition of $P$ into cells such that the link distance from $s$ to any point within one cell is the same. Note that it is not required that the cells of LDM are maximal (i.e., that the link distance necessarily changes as you step from a cell to a neighboring cell): the only requirement is that the distance never changes within a cell.

For simple polygons, an LDM is really a by-product of the staged illumination (the edges of the map are the windows). Both a single minlink path and the LDM can be computed in $O(n)$ time (because in a simple polygon the windows are pairwise disjoint, the LDM in it is also called a “window partition” [28, 4]).

In polygons with holes the LDMs can have $\mathrm{\Omega }(n^4$) complexity [29], and extra care must be taken in order to produce the LDM. In [25, Theorem 12] it was shown how to build the LDM in $\tilde{O}(n^5)$ time, where $\tilde{O}$ notation suppresses polylogarithmic factors. The map is defined by an arrangement of windows (called “illumination edges” in [25]) within the domain.

Similarly to constructing an LDM from a point, one can build LDM from a source chord $c$ of $P$ (Fig. 3): the weak VP of $c$ is the set of points reachable with 1 link from $c$, and the subsequent steps of the illumination are defined in the same way as for a point source. LDMs from segments were built already in early work [28] on link distance; in particular, LDMs from chords were used for finding the link center of a simple polygon [11].

After being preprocessed for point location, an LDM allows one to report the link distance from the source to a query point $q$ in optimal $O(\log n)$ time, by locating the cell of the map that contains $q$ (enhanced with the backpointers, the map lets one report an actual minlink path in the additional time proportional to the number of links). An LDM is thus analogous to the shortest-path map (SPM($s$)) in $P$, which decomposes the domain into cells such that the length of the geodesic (shortest) path from $s$ to any point in one cell is given by the same formula. Note that while SPMs have linear complexity and can be built in linear (for simple polygons) or near-linear (for polygons with holes) time [34, 33], finding even a single minlink path in polygons with holes is 3SUM-hard [24] (an $\tilde{O}(n^2)$-time algorithm is given in [25]).

Computing the diameter and radius is intimately connected to the 2-point distance query structures, described above, via the following observation applicable to both geodesic and link distances – hence the prefix Meta:

Solutions based on MetaTheorem 1 are not very efficient, and faster algorithms exist for finding both the geodesic diameter [6] and radius [31] of polygonal domains (in simple polygons, linear-time algorithms exist for both geodesic diameter [18] and radius [3]; link diameter [27] and radius [11] of simple polygons can be found in near-linear time). Existing results regarding diameter and radius are summarized in Table 1: essentially, the only case that has been missing is link distance in polygons with holes. Similarly, for simple polygons 2-point distance query data structures are known both for geodesic [16] and link distance [4], while for polygonal domains the problem has been solved only for the geodesic distance [9].

In this paper, we fill the gaps by showing how to construct the 2d map equivalence decomposition of a polygonal domain $P$ and the 4d distance equivalence decomposition of $P\times P$ under the link distance. By MetaTheorem 1, this leads to polynomial-time algorithms for finding the link diameter and radius/center of the domains $P$.

The rest of the paper is organized as follows. Section 4 gives a simple algorithm to compute the link diameter (without resorting to MetaTheorem 1), and Section 5 presents data structures for 2-point link distance queries. Our data structures reuse, extend and combine the techniques of [4] (link distance queries in simple polygons) and [9] (geodesic distance queries in polygonal demands with holes): analogously to [9], our data structures are the 2d LDM equivalence decomposition and the 4d link distance equivalence decomposition. We conclude in Section 6 with some open problems.

For a line segment $\mathrm{\ell }$ in $P$ let $\overline{\mathrm{\ell }}$ be the chord of $P$ containing $\mathrm{\ell }$ (i.e., $\overline{\mathrm{\ell }}$ is $\mathrm{\ell }$ extended maximally within $P$). Define the Extended Visibility Graph EVG = {$\overline{uv}:uv$ is an edge of VG} as the set of chords of $P$ obtained by maximally extending every edge of VG (we remind that edges of $P$ are also edges of VG).

Recall [25, Section 8] (see also Section 2.3) that an LDM is defined by an arrangement of windows together with edges of $P$. Recall also that there is no requirement that the cells of LDM are maximal (i.e., that the link distance necessarily changes as you move between cells) – the only requirement is that the distance never changes within a cell. Thus LDM($s$), for some point $s\in P$, remains LDM($s$) even if one subdivides its cells into smaller pieces.

For the rest of the paper, we redefine LDM to include all chords of EVG. That is, we refine LDM by chords of EVG (but we continue to call the result LDM). In other words, we assume that EVG chords are windows of LDM($s$) for any $s$: we thus use the term “windows” to refer both to “original” windows of LDM (as defined in [25]) and chords of EVG.

Every window $w$ necessarily goes through a vertex of $P$ (Fig. 4). If the chord $\overline{w}$ goes through another vertex ($\overline{w}\in$ EVG), we call $w$ a pinned window – such windows do not change as $s$ moves locally; in particular, chords of EVG are pinned windows. Otherwise we call $w$ a bash window, and the endpoints of $\overline{w}$ – bash points. A bash point lies in the interior of an edge of $P$; we call such an edge a bash wall. (The term “pinned” is borrowed from [4] where analogous edges were called “(rotationally) pinned”; the term “bash” is borrowed from [22] where path vertices lying in the interior of polygon edges were called “bash points” and the edges were called “bash walls”.)

As $s$ moves slightly, pinned windows of LDM($s$) do not change. A bash window $w$ may remain still or may rotate, depending on whether there is a pinned window appearing on the greedy path from $s$ to $w$ (recall from Section 2.2 that a greedy path is the minlink path following the windows):

Static bash windows.

Any bash window $w$ appearing after a pinned window $w^{\prime }$ does not move with $s$ because $w$ is a window in LDM($\overline{w^{\prime }}$) and $w^{\prime }$ does not move with $s$.

Rotating bash windows (bash-bash windows).

If all windows preceding $w$ are bash windows, then they all rotate around vertices of $P$, with the bash points (which are the bend points of the greedy path from $s$ to $w$) sliding along the bash walls; we call such windows bash-bash windows and the greedy path from $s$ to $w$ a bash path. (Refer to Fig. 4 – as $s$ moves left, all windows rotate, so they are bash-bash windows: in fact, it is exactly bashing that leads to high bit complexity of minlink path vertices and that makes studying minlink paths challenging, as the bash points do not lie on any predefined structure which could be computed from $P$ – differently from, e.g., geodesic paths which follow a VG.)

Overall, we obtain the classification of LDM windows into static and rotating. The former may be EVG chords or static bash windows; the latter are bash-bash windows.

We build LDMs from all chords of the EVG; let $W_{\mathrm{EVG}}$ denote the set of all windows in these LDMs. The first step in constructing our data structures is computing the overlay $𝒪$ of the windows in $W_{\mathrm{EVG}}$. That is, we compute the overlay of LDMs from all chords of EVG – this is the same as [4] did, but we build the full overlay of the LDMs, while [4] considered only the interaction of $W_{\mathrm{EVG}}$ with the boundary of $P$.

Consider LDM($s$) for a point $s$ in $P$. As $s$ moves, the bash-bash windows of LDM($s$) rotate and the map may change combinatorially when either

Simple case.

A window hits a vertex of $P$ (aligning itself with a VG edge) when $s$ crosses an edge of $𝒪$, or

New case.

The arrangement of the windows changes because 3 windows pass through a common point (out of the 3 windows, at least one must be a rotating window).

We called the first event “simple” because this is the only thing that may happen in a simple polygon (where windows are pairwise disjoint). As we will show in Section 5.10, to account for new events one needs to build LDMs from intersection points of windows in $W_{\mathrm{EVG}}$, as well as to do some additional, less straightforward computations described later.

An important connection between the overlay $𝒪$ and static windows in LDMs is that all possible static windows in an LDM from any point of $P$ are known in advance:

Edges of $𝒪$ (windows of $W_{\mathrm{EVG}}$) split the edges of $P$ into segments called atomic in [4] (note that vertices of $P$ are endpoints of atomic segments too). Since any atomic segment $a$ fully belongs to a single cell in $𝒪$, for all points $s\in a$, LDM($s$) has combinatorially the same bash paths. Moreover, the exact location of the bash points (vertices of the paths) and hence the directions of the rotating bash-bash windows in LDM($s$) depend on the location of $s$ in $a$ via “projection” functions worked out in [4] which further refers to [2] for details of computing the functions: any projection function is the ratio of 2 linear functions of $s$, whose parameters can be calculated window-by-window in constant time per window.

If the new cases are ignored, then LDMs (with the corresponding projection functions) built for all cells of $𝒪$ define the 2d LDM equivalence decomposition. The data structure can be used to answer 2-point link distance queries in the same way as the 2d SPM equivalence decomposition [9, Section 4.2] answers geodesic distance queries: given query points $s$ and $t$, first $s$ is located in a cell $\sigma$ of $𝒪$ and then $t$ is located in the parametric LDM($s$).

In fact, since LDM edges (the windows) are straight line segments (not hyperbolic arcs as edges of SPM), one possibility for locating $t$ in the parametric LDM($s$) is to use the monotone subdivision method of [12]. Indeed, each comparison needed to answer the point location query for $t$ using [12], can be done in constant time even when the edges of the monotone subdivision $ℳ$ are constant-algebraic-complexity functions of $s$, as long as $ℳ$ remains the same topologically (i.e., as long as the horizontal ordering of its vertices remains fixed). Since we know, via the projection functions, how LDM($s$) changes, we also know how $ℳ$ changes with $s$. In particular, we can compute the locus $S\in \sigma$ of positions for $s$ at which 2 vertices of $ℳ$ have the same $x$-coordinates: for any 2 vertices $u,v$ of $ℳ$, this amounts to solving for $s$ the constant-degree polynomial equation $x_v(s)=x_u(s)$ where $x_u,x_v$ are the abscissae (i.e. the $x$-coordinates) of $u,v$. After refining $\sigma$ by such sets $S$ for all pairs of vertices of $ℳ$, we obtain the required subdivision in which parametric point location query, and hence the link distance query, can be answered in time logarithmic in the complexity of $ℳ$. Since the complexity of LDM and hence the complexities of $𝒪$ and $ℳ$ are polynomial in $n$, the query time is $O(\log n)$.

We can also build the decomposition $𝒪\times 𝒪$ of the 4d $P\times P$ space. That is, for any point $(s,t)\in P^2$ within one cell $\rho$ of ${𝒪}^2$, we have $s\in \sigma ,t\in \tau$ where $\sigma ,\tau$ are some cells of $𝒪$. Via the projection functions, we know how each window $w$ of LDM($s$) depends on $s$. In 4d, the union ${\bigcup }_{s\in \sigma }w(s)$ of the windows $w$ as $s$ varies over $\sigma$ defines a surface of constant algebraic degree, which we call a curtain (the surface is swept by the rotating $w$: as $s$ moves along a ray from a vertex $v$ of $P$, the window stays the same; the window rotates as $vs$ rotates about $v$). We build the arrangement of the curtains in $\rho$, and repeat it for all cells $\rho$ of ${𝒪}^2$. In the obtained decomposition (cells of ${𝒪}^2$, decomposed by the curtains) the link distance between any pair of points ($s$, $t$) from one cell is the same: the link distance between $s$ and $t$ may change only if $t$ crosses a window of LDM($s$), which happens only if $t$ (the last two coordinates of point ($s$, $t$) in 4d) crosses a curtain. To achieve $O(\log n)$ query time, preprocess the decomposition for point location (e.g., in the same way as was done for geodesic queries in [9, Theorem 3.1]).

What remains is to account for the new cases (windows arrangement changes due to 3 windows passing through a common point). In Section 5.10 we give an algorithm to compute the locations $𝒮\subset P$ for $s$ such that 3 windows in LDM($s$) may intersect in a common point $t$ ($𝒮$ consists of curves of constant algebraic degree ). The set $𝒮$ is overlaid with $𝒪$. By construction, for all points $s$ in one cell of the obtained 2d overlay ${𝒪}^{\ast }$, LDM($s$) is the same combinatorially: it has the same windows and they form the same arrangement (before the arrangement changes, 3 windows must pass through a common point, at which moment $s$ is in $𝒮$). Our final data structure, the (full) 2d LDM equivalence decomposition (“full” in the sense that it accounts for both simple and new cases) is built from ${𝒪}^{\ast }$ in the same way as the data structure for handling simple cases was built from $𝒪$ (Section 5.6).

As a by-product of computing $𝒮$, we also identify the corresponding locations for the “triple points” $t$, thus obtaining the (super)set $𝕊\subset P\times P$ of pairs ($s$, $t$) of potential triple points. Then, (super)set $𝕊$ is overlaid with ${𝒪}^2$ subdivided by the curtains (Section 5.7). For all $(s,t)$ in one cell of the obtained 4d overlay $\widehat{𝒪}$, the $s$-$t$ distance is the same. Preprocessing $\widehat{𝒪}$ for point location, we obtain our other data structure – the (full) 4d link distance equivalence decomposition (“full” in the sense that it accounts for both simple and new cases).

To find the set $𝒮$ of sources potentially having triple points in their LDMs, we build yet another decomposition and do some preparation work. In [25], the combinatorial type of a window $w$ was defined as the pair $(v,e)$ where $v$ is the vertex of $P$ at which $w$ begins and $e$ is the edge on which the window ends. We refine the definition by saying that the window’s combinatorial type is a pair $(v,a)$ where $a$ is the atomic segment on which $w$ ends. We decompose $P$ by rays from every atomic segment endpoint through every vertex visible to the endpoint (recall that vertices of $P$ are also endpoints of atomic segments). For any point $s$ in a cell of this decomposition $𝒟$ and every vertex $v$ visible to $s$, the atomic segment $a$ hit by the ray $sv$ is the same; let $s^{\prime }=s^{\prime }(s)\in a$ be the point where the ray hits the segment (we write $s^{\prime }=s^{\prime }(s)$ to emphasize its dependence on $s$). Since $a$ fully belongs to a single cell of the overlay $𝒪$, the map LDM($s^{\prime }$) from any point $s^{\prime }\in a$ has combinatorially the same bash-bash windows; moreover, the dependence of these windows on $s^{\prime }$ (and hence on $s$) is known via the projection functions. We thus write $w=w(s)$ for a window $w$ in LDM($s^{\prime }$).

We are now ready to compute the (super)set $𝒮$ of points $s$ for which LDM($s$) may have a triple point $t$; the corresponding locations for $t$ (i.e., the set $𝕊\subset P\times P$ for the pairs ($s$, $t$) defining the 4d link distance equivalence decomposition) are computed as well. We emphasize that we do not claim that LDM($s$) has a triple point for every $s$ in $𝒮$ (or that $\forall (s,t)\in 𝕊$ LDM($s$) has a triple point at $t$); we only claim that $𝒮$ is sufficiently rich to “catch” all possible (sources of) maps with triple points (and that $𝕊$ includes all pairs of triple points).

Let $w_1,w_2,w_3$ be windows of LDM($s$) that intersect at $t$, of which at least 1 window rotates (so that LDM($s$) changes combinatorially when the 3 windows intersect at $t$). Recall from Observation 2 that the (super)set $W_{\mathrm{EVG}}$ of possible static windows in LDM($s$) does not depend on $s$. We make 3 different guesses on how many of the 3 windows $w_1,w_2,w_3$ are rotating (1, 2, or all 3), and do different things for each of the guesses (Fig. 5):

• $\mathrm{■}$

  Assuming only $w_1$ is rotating, LDM($s$) changes when $w_1$ passes through $t=w_2\cap w_3$ (the intersection point of two static windows $w_2,w_3$). At this point there is a bash path between $s$ and $t$, implying that $s$ is on a bash-bash window of LDM($t$). We thus build LDM($t$) from every intersection point $t$ of two (potential) static windows $w_2,w_3\in W_{\mathrm{EVG}}$ and add to $𝒮$ all bash-bash windows of LDMs; the 4d set $𝕊$ is correspondingly appended with the Cartesian product of $t$ and all bash-bash windows of LDM($t$).

• $\mathrm{■}$

  Assuming 2 windows (say, $w_1,w_2$) are rotating, LDM($s$) changes when their intersection point $t$ passes through $w_3$. At this point there are two bash paths between $s$ and $t$ (in one path $t\in w_1$, in the other $t\in w_2$). That is, $s$ is the intersection point of two rotating windows in LDM($t$) (one window belonging to the bash path from $t$ that starts from following $w_1$; the other – following $w_2$). We thus take every window $w_3\in W_{\mathrm{EVG}}$ as the potential static window in LDM($s$) and intersect it with every cell $\tau$ of $𝒪$; let $w_3^{\tau }$ denote part of $w_3$ inside $\tau$. For all points $t\in w_3^{\tau }$, LDM($t$) has the same set of windows, and in particular, the same set of bash-bash windows; each window is a known function of $t$ (via the projection functions). For every pair of the bash-bash windows (with the same link distance from $t$) in LDM($t$) we add to $𝒮$ the curve traced by their intersection as $t$ varies along $w_3^{\tau }$; the 4d set $𝕊$ is correspondingly appended with the Cartesian product of $w_3^{\tau }$ and the intersection points for $t\in w_3^{\tau }$.

• $\mathrm{■}$

  Assuming all 3 windows are rotating, we go through all pairs of cells $\sigma ,\tau$ in $𝒟$, guessing that $s\in \sigma ,t\in \tau$. In addition, we go through all triples $v_1,v_2,v_3$ of vertices visible from $s$ and all triples $u_1,u_2,u_3$ of vertices visible to $t$, guessing that the vertices support the first and the last windows resp. of the 3 bash paths (ending with the windows $w_1,w_2,w_3$) between $s$ and $t$. Since vertices of $P$ are endpoints of atomic segments, the decomposition $𝒟$ includes chords of EVG, implying that the set of vertices visible to any point in a cell of $𝒟$ is the same: it is thus valid to speak about a triple of vertices visible to $s\in \sigma$ or to $t\in \tau$ without specifying the exact locations of $s$ and $t$ in the cells.

  Using the projection functions, we know whether for some number $k$ of links there indeed exist 3 length-$k$ bash paths from $s$, with the first links of the paths supported by $v_1,v_2,v_3$ and last links supported by $u_1,u_2,u_3$. If yes, let $w_1(s),w_2(s),w_3(s)$ be these last links (windows of LDM($s$)). For $t$ to be a triple point, the system

  $$\{\begin{array}{cc}t\in w_1(s)\hfill & \\ t\in w_2(s)\hfill & \\ t\in w_3(s)\hfill & \end{array}$$

  (1)

  of 3 equations (each involving the projection function) with 4 unknowns (the coordinates of $s$ and $t$) must be satisfied (for $s\in \sigma ,t\in \tau$). We solve the system and obtain the decompositions both for the 2d LDM equivalence decomposition (the set $𝒮\subseteq P$ such that LDM($s$) may change combinatorially only when $s$ is crossing $𝒮$, see Fig. 5 for an example of such a combinatorial change) and for the 4d link distance equivalence decomposition (the surface $𝕊\subseteq P^2$ such that the link distance between $s$ and $t$ may change only when ($s$, $t$) is crossing $𝕊$). That is, the 4d set $𝕊$ consists of pairs ($s$, $t$) satisfying (1), while for the 2d set $𝒮$ we take only the first two coordinates of the 4d pairs ($s$, $t$) (i.e., the coordinates for $s$; the knowledge of corresponding locations for $t$ is ignored).

We summarize the steps described above, needed to build our data structures:

1. 1.

   Build VG and EVG (Section 5.1).

2. 2.

   Designate all chords of EVG as (static) windows in any LDM ever built (Section 5.2).

3. 3.

   Compute the set $W_{\mathrm{EVG}}$ of windows in LDMs from all chords of EVG (any static window in any LDM is part of $W_{\mathrm{EVG}}$) and compute the overlay $𝒪$ of the LDMs (Section 5.4).

4. 4.

   Identify atomic segments by intersecting $𝒪$ with the boundary of $P$ (Section 5.5).

5. 5.

   For each atomic segment $a$, compute the projection functions specifying the windows in LDM($s$) $\forall s\in a$ (Section 5.5). The functions are used to identify the 2d set $𝒮\subset P$ of potential triple points and the 4d set $𝕊\subset P^2$ of potential pairs of triple points of LDMs, as well as to answer link distance queries with parametric LDMs.

6. 6.

   Build the decomposition $𝒟$ of $P$ by using rays from atomic segments though vertices of $P$ (Section 5.9). $𝒟$ is an auxiliary structure: we do not overlay $𝒟$ with any other decomposition and do not use it in our final data structures; $𝒟$ is used only to compute the 2d set $𝒮\subset P$ of potential triple points and the 4d set $𝕊\subset P^2$ of potential pairs of triple points – these sets will be used in our data structures, refining $𝒪$ and ${𝒪}^2$ respectively.

7. 7.

   Compute the sets $𝒮$ and $𝕊$ for triple points: build LDMs from intersection points of windows from $W_{\mathrm{EVG}}$, track intersections of windows in LDM($t$) as $t$ varies along each window from $W_{\mathrm{EVG}}$, go through all triples of windows in pairs of cells of $𝒟$ (Section 5.10).

8. 8.

   Build the overlay ${𝒪}^{\ast }$ of $𝒪$ with $𝒮$ (Section 5.8). To obtain the 2d LDM equivalence decomposition data structure, preprocess ${𝒪}^{\ast }$ for parametric point location, e.g., by further decomposing the cells of ${𝒪}^{\ast }$ so that for all $s$ in one cell of the refined decomposition, the ordering of $x$-coordinates of vertices of LDM($s$) is the same (as done in Section 5.6 for $𝒪$).

9. 9.

   Decompose $𝒪\times 𝒪$ by curtains (Section 5.7) and overlay the decomposition with $𝕊$, getting 4d decomposition $\widehat{𝒪}$ (Section 5.8). To obtain the 4d distance link equivalence data structure, preprocess $\widehat{𝒪}$ for point location queries.