Realizing Metric Spaces with Convex Obstacles

Before discussing our obstacle placement, we first describe the construction of $𝒮$ and the embedding $f$. (Note that the main text will define the surface $𝒮$ last.) First, without loss of generality we assume that the minimum distance in $(X,{\mathrm{dist}}_X)$ is at least some large polynomial in $n:=|X|$, as we can use a scaling on the final construction to get the desired distance. The function $f$ simply assigns the points $x_i$ to equally spaced points along the $x$-axis. The surface $𝒮$ will contain a cube ${ℛ}_i$ centered at each point $f(x_i)$.

For each pair $i,j$ we realize the distance of ${\mathrm{dist}}_X(x_i,x_j)$ via a sequence of three tubes (cylinders), where the first and third cylinder are vertical (parallel to the $z$-axis) and the second is parallel to the $x$-axis, see Figure 2. The tubes connect a hole in the top of the cube ${ℛ}_i$ to a hole on the cube ${ℛ}_j$, and in order to realize the turns, we use two small cubes with holes that connect the first and second as well as the second and third tube in the sequence. Notice that the the length of the second horizontal tube is determined by $f(x_i)$ and $f(x_j)$, thus in order to set the length of the cube sequence, we can vary the length of the two vertical tubes. We place these tubes at different depths ($y$-coordinates) so that they remain disjoint from each other. One can see that this leads to a good approximate realization, however, this surface needs to be smoother (differentiable) in order to ease the placement of obstacles. Thus $𝒮$ is defined using differentiable surface patches: we need a rounded cube and a differentiable joint that allows the connection of a flat cube face with a circular cylinder boundary.

Let us consider an example of a simple placement of convex objects that increases the geodesic distance between the half-space and the half-space $z>1$ to significantly more than $1$. We call this construction a flat wall. In this construction we use squares rather than triangles. Let $S_1$ be the set of axis-parallel squares of side length $0.99$ centered at the points $(a,b,0.01)$ for $a,b\in \mathbb{Z}$ in the $z=0.01$ plane. Repeat the same construction $3$ more times at heights $z=0.02,0.03,0.04$ by translating $S_1$ with the vectors $(1/2,0,0.01),(1/2,1/2,0.02),(0,1/2,0.03)$, to get the sets $S_2,S_3$, and $S_4$, respectively. See Figure 1(ii) and (iii). Consider a geodesic connecting the planes $z=0$ and $z=0.05$: its intersection point $p$ with $z=0$ will be within ${\mathrm{\ell }}_{\mathrm{\infty }}$-distance $0.25$ to the center of some square in one of the four shifts, and thus it will need to have length at least $0.24$ to reach the boundary of this square before it can get to $z=0.05$. Using further copies of these squares shifted to different height ranges can increase the lower bound of $0.24$ as necessary. By making more layers that are packed more densely we can achieve any separation between the halfspaces and $z>1$.

While the above construction is quite intuitive, we need a more careful approach to make a similar separation near an embedded closed surface. One can see that the flat construction cannot be adapted to a surface with sharp edges, so we will need to use a smoother closed surface. Even then, we will not be able to place layers of convex objects arbitrarily close together, as convex $2$-dimensional shapes will not stay inside a curved surface. The challenge is to keep our objects in different layers disjoint, while creating a strong separation.

The surface $𝒮$ that we define has the crucial property that it has offset surfaces (often called parallel surfaces) that are well-defined and differentiable for any distance offset $\delta \in [-1/2,1/2]$ from $𝒮$. The offset surface at distance $\delta$ is denoted by $𝒮(\delta )$. Since $𝒮(\delta )$ is a closed surface, we are able to talk about the inside and outside of $𝒮(\delta )$, and we can also define the region between two offsets $𝒮(\delta )$ and $S({\delta }^{\prime })$ when . In our construction, the offset $\delta$ will have a role similar to the $z$-coordinate in the flat wall construction above: we will place triangles tangent to $S(\delta )$ at some given collection of points. Using a large collection of different offsets, we can ensure the required separation between the inside of $𝒮(-1/2)$ and the outside of $𝒮(1/2)$.

We need a handful of geometric properties from $𝒮(\delta )$ to ensure that we can place our obstacles near it. The most important property is to limit their curvature¹¹1While our results could be presented with a more general differential geometric toolbox, the need to construct these $(a,b)$-nets prompted us to use specific surface patches that are easy to handle algorithmically. One could adapt our techniques to more general smooth embedded surfaces. As a trade-off our surfaces are not smooth (not even twice differentiable) at the shared boundary of our surface patches. We have also used the Euclidean distance function rather than measuring distances within these surfaces to make our construction more elementary and explicit. in some sense. We require that at any point $p$ on $𝒮(\delta )$ there exist two balls of radius at least $1/2$ whose unique intersection point with $𝒮(\delta )$ and with each other is $p$. This helps to ensure that a small $2$-dimensional convex shape of diameter $\mu \ll 1$ tangent to $𝒮(\delta )$ at $p$ stays within distance $O({\mu }^2)$ of $𝒮(\delta )$. In particular, a small triangle will stay between the surfaces $𝒮(\delta -{\mu }^2)$ and $𝒮(\delta +{\mu }^2)$, and thus triangles of the same size tangent to $𝒮(\delta -2{\mu }^2)$ and $𝒮(\delta +2{\mu }^2)$ will remain disjoint from this triangle.

Finally, we must place the triangles in neighboring layers with “shifts” to ensure that a constant number of consecutive triangular layers of side-length $\mu$ triangles creates a separation of at least $\mathrm{\Omega }(\mu )$. Here translation is not an option, so we define an $(a,b)$-net, a weaker version of an $\epsilon$-net (in the metric space sense). For two points $u,v\in {ℝ}^3$ we will denote by $uv$ the line segment between $u$ and $v$, and by $|uv|$ the length of $uv$. An $(a,b)$-net of a surface $𝒮$ embedded in ${ℝ}^3$ is a point set $N\subset 𝒮$ where the pairwise distance of points in $N$ is at least $a$, and for any point $q\in 𝒮$ there is a $p\in N$ such that $|pq|\le b$.

We can show that the offsets of the net points provide a weaker but still useful net in the offset surfaces: a “shared” $(\mathrm{\Omega }(\zeta ),O(\zeta ))$-net can be constructed for the surfaces $𝒮(\delta )$. Here, “shared” means that we first find a $(\zeta ,O(\zeta ))$-net on $𝒮$; sliding every net point along its surface normal gives, on each surface $𝒮(\delta )$, an $(\mathrm{\Omega }(\zeta ),O(\zeta ))$-net. These net points are then partitioned into constantly many classes, where the distances within points in each class $C$ are large enough so that equilateral triangles of side length $\mu =\mathrm{\Theta }(\zeta )$ tangent to $𝒮(\delta )$ at each point of $C$ will remain disjoint; i.e., these triangles would correspond to a single square set $S_1$ from our flat wall example. Using all of these partition classes in different offsets $𝒮(\delta +i\zeta )$ ensures a separation of $\mathrm{\Omega }(\zeta )$ for geodesics passing between these layers, as seen with the four shifts of squares in our flat wall example. In our construction we must set $\zeta$ small enough to be able to accommodate several iterations of the above construction between $𝒮(-1/2)$ and $𝒮(1/2)$, but large enough to get the desired length lower bound for any geodesic going from the inside of $𝒮(-1/2)$ to the outside of $𝒮(1/2)$. This concludes the generic construction of the curved wall, as well as the overview of the ideas behind Theorem 3.

Note that due to the condition , the offset surfaces $𝒮(\delta -2{\epsilon }^2)$ and $𝒮(\delta +2{\epsilon }^2)$ are well-defined. Moreover, we have that $\frac{1}{2}-2{\epsilon }^2>0$, or equivalently that .

For the following refer to Figure 4. Consider the tangent balls $B_1,B_2$ of radius $\frac{1}{2}$ that touch $𝒮(\delta )$ at $p$ and consider the line $\mathrm{\ell }$ through $q$ parallel to $𝐧(p)$. Since , the line $\mathrm{\ell }$ intersects $B_1$. Let $q_1$ denote the point closest to $q$ in $B_1\cap \mathrm{\ell }$. Similarly, $\mathrm{\ell }$ will also intersect $B_2$ and let $q_2$ denote the point closest to $q$ in $B_2\cap \mathrm{\ell }$. Because $𝒮(\delta )$ is $1/2$-touchable, we have that the interiors of $B_1$ and $B_2$ cannot both be inside or both be outside $𝒮(\delta )$, thus $q_1{q}_2$ intersects $𝒮(\delta )$. In particular, $q_{1}q$ or $q_{2}q$ has to intersect $𝒮(\delta )$; we assume without loss of generality that $q_{1}q$ intersects $𝒮(\delta )$ at a point $q^{\ast }$. Since , it suffices to show that $|q_{1}q|\le 2{\epsilon }^2$.

Let $o$ denote the center of $B_1$ and choose $q_3$ in the extension of $q_{1}q$ towards $q_1$, such that $|q_{3}q|=\frac{1}{2}$. Then in the right triangle $\mathrm{△}o{q}_1{q}_3$ we have: ${|pq|}^2+{\left(\frac{1}{2}-|q_{1}q|\right)}^2={\left(\frac{1}{2}\right)}^2$, which gives: $|q_{1}q|=\frac{1}{2}-\sqrt{{\left(\frac{1}{2}\right)}^2-{|pq|}^2}$. (The other root of the equation would lead to $|q_{1}q|>1/2$, but this is not possible as $q_{1}q$ is shorter than the radius of $B_1$.) Thus:

where in the second inequality above, we have used that $\sqrt{1-x^2}\ge 1-x^2$, for $x\in [0,1]$. $◀$

First note that . Moreover, any cylinder patch of $𝒮(\delta )$, has distance at least $1/2$ from any square patch of $𝒮(\delta )$. Therefore, $B(p,t\cdot \zeta )$ cannot intersect both a square and a cylinder patch at the same time. Recall that any two holes on a square patch have pairwise distance at least $6$ and are also at distance at least $2$ from the boundary of the square patch. Therefore, $B(p,t\cdot \zeta )$ cannot intersect both a quarter-cylinder patch and a joint or a cylinder patch at the same time. The highest number of distinct surface patches $B(p,t\cdot \zeta )$ can intersect is $7$, which may happen when it intersects a spherical triangle patch and the three quarter-cylinder patches around it and the three square patches around it. Since it can intersect at most a constant number of distinct patches, it suffices to show that it can contain at most $O(t^2)$ points of $N_{\delta }$ from each different type of surface patch.

To that end, let $𝒫$ denote a patch which is not a square patch and not a spherical triangle patch. For the remaining types of patches, the constructed net is taken as a point set of the form $I(A,B)$, where elements in $A$ and $B$ are quarter-circular arcs, line segments or circles. In all cases, we have argued already that any two elements in $A$ have distance at least $\zeta /2$ (since now $N_{\delta }$ is a $(\zeta /2,12\zeta )$-net) and any two elements in $B$ have also distance at least $\zeta /2$. Therefore, from any point $p\in 𝒫$ and within distance $t\cdot \zeta$, we can reach at most $2t$ elements of $A$ and $2t$ elements of $B$. Therefore we can reach at most $4t^2$ net points of $𝒫$. On a spherical triangle patch, the arcs of $A$ again have pairwise distance at least $\zeta /2$, so we can reach at most $O(t)$ arcs, and on each arc we can reach at most $O(t)$ points as on each quarter-circular arc the distance between consecutive points is at least $\zeta /2$.

For a square patch, the process of construction was slightly different due to the existence of the holes. Using the same argumentation as above, we can deduce that $B(p,t\cdot \zeta )$ can contain at most $4t^2$ net points from the initially placed grid. Moreover, $B(p,t\cdot \zeta )$ can intersect at most one hole. Note that a single hole contains $O(1/\zeta )$ net points and since , it contains at most $O(t)$ net points. Therefore, $B(p,t\cdot \zeta )$ can contain at most $5t^2$ net points of a square patch.

Since we argued that $B(p,t\cdot \zeta )$ can intersect at most $7$ distinct surface patches, we have that it can contain at most $7\cdot 5t^2=35t^2$ points of $N_{\delta }$.

For the second part of the lemma create $b=\lfloor 35t^2+1\rfloor$ partition classes $N_{\delta ,1},N_{\delta ,2},\mathrm{\dots },N_{\delta ,b}$ and greedily place points in these classes: we place each point $p\in N_{\delta }$ in the available class of smallest index (that is, a class of minimum index not already containing any point $q$ such that ). Note that in this way, there will always be a class which is available, since for any point there are at most $35t^2$ points that cannot be in the same class with it. $◀$

By applying Lemma 8 and Lemma 9 for we obtain a $(\zeta /2,12\zeta )$-net $N_{\delta }$ of $𝒮(\delta )$ of size $O(\mathrm{area}(𝒮)/{\zeta }^2)$. We set $t=48(1+\sqrt{3})$, and choose $\nu$ large enough such that . Then, by Lemma 10, we can partition $N_{\delta }$ into $b=\lfloor 35t^2+1\rfloor$ classes ${(N_{\delta ,i})}_{i=1}^b$, where points within each class $N_{\delta ,i}$ have pairwise distance at least $t\cdot \zeta =48(1+\sqrt{3})z$. We will now place each class $N_{\delta ,i}$ on a different offset $𝒮({\delta }_i)$, defined as follows. We start by setting $\nu =4b+1$ and define ${\delta }_i:=\delta +4i\cdot {\zeta }^2$, for $i=1,2,..,b$. From now on, we consider the points of each class $N_{\delta ,i}$ on the surface $𝒮({\delta }_i)$ defined as above.

The above definition ensures . Thus, the offsets $S({\delta }_i)$ are well-defined. Furthermore, we also have the following:

For $1\le i\le b$ and $p\in N_{\delta ,i}$, let $T_p$ denote the equilateral triangle of side length $48\sqrt{3}\zeta$ centered at $p$, which lies on the tangent plane $H_p$ at $p$. Let ${𝒯}_i=\{T_p:p\in {𝒩}_{\delta ,i}\}$ and $𝒯={\bigcup }_{i=1}^b{𝒯}_i$. We now argue that $𝒯$ satisfies the three properties of the Lemma:

1. (i)

   This holds trivially since .

2. (ii)

   Lemma 7 together with (1), ensure that any two triangles in $𝒯$ that belong to different offsets are disjoint. Next, we argue that any two triangles $T_p,T_q\in {𝒯}_i$ are disjoint. From Lemma 10 we know that $|pq|\ge 48(1+\sqrt{3})\zeta >96\zeta$. Since each of our triangles has circumradius $48\zeta$, it follows that $T_p,T_q$ cannot intersect.

3. (iii)

   Refer to Figure 5 for an illustration. Let $p\in 𝒮(\delta )$ and $q\in 𝒮(\delta +\nu {\zeta }^2)$ and consider a shortest geodesic path $\pi (p,q)$. We want to show that ${\mathrm{dist}}_{𝒯}(p,q)\ge c\cdot \zeta$ for some constant $c$. Let $u$ be a point in $\pi (p,q)\cap 𝒮({\delta }_1)$ and consider the segment $s$ between the points $u-𝐧(u)$ and $u+𝐧(u)$. We consider the following two cases:

   • $\mathrm{■}$

     Case I: There exists $v\in \pi (p,q)$, such that ${\mathrm{dist}}_{{ℝ}^3}(v,s)\ge 4\zeta$.
     Then $\pi$ has the desired length.

   • $\mathrm{■}$

     Case II: $\pi (p,q)$ is contained in the cylinder with axis $s$ and radius $4\zeta$
     Let $𝒞(ab,x)$ denote the cylinder of axis $ab$ and radius $x$. We will show that there exists $T\in 𝒯$ which cuts the cylinder $𝒞(s,4\zeta )$ in such a way that the top and bottom disk of the cylinder are completely contained in different sides of the cut. Since $\pi (p,q)$ connects these disks and it is disjoint from all triangles $T\in 𝒯$, this will give a contradiction.

     By the properties of $N_{\delta }$, we know that there exists a surface $𝒮({\delta }_i)$, such that $s\cap 𝒮({\delta }_i)$ is within distance $12\zeta$ from a point $w\in N_{\delta ,i}$. We will argue that $T_w$ is the required triangle. Towards that, let $s_i=s\cap 𝒮({\delta }_i)$ and recall that $T_w$ has inradius $24\zeta$ and denote by $D$ the incircle of $T_w$. Observe that $𝒞(s_{i-1}{s}_{i+1},4\zeta )\subset B(w,24\zeta )$. By Lemma 7, we know that $T_w$ is between $𝒮({\delta }_{i-1})$ and $𝒮({\delta }_{i+1})$. Since $D$ splits $B(w,24\zeta )$ in two pieces where $s_{i-1}$ and $s_{i+1}$ are in different parts, we get that $D$ has to cut $𝒞(s_{i-1}{s}_{i+1},4\zeta )$. We conclude that indeed $T_w$ cuts $𝒞(s,4\zeta )$ in the described manner, which is a contradiction.

$◀$

By iterating the construction of Lemma 11 we get our curved wall separation theorem.

We need to upper and lower bound the length of a geodesic from $f(x_i)$ to $f(x_j)$. The choice of $\sigma$ ensures that we only need to consider geodesics within $𝒮(1/2)$. We set ${\mathrm{\ell }}_{\mathrm{vert}}(i,j)$ so that any geodesic that passes through the three-cylinder-tube connecting ${ℛ}_i$ and ${ℛ}_j$ has length at least ${\mathrm{dist}}_X(x_i,x_j)$. Now a geodesic passing through multiple such tubes will have a length that is at least the sum of the corresponding distances, thus by the triangle inequality in $X$ any such path will also have length at least ${\mathrm{dist}}_X(x_i,x_j)$.

To upper bound the geodesic distance of $f(x_i)$ to $f(x_j)$, we observe that there is a direct path in $𝒮(-1/2)$ connecting $f(x_i)$ and $f(x_j)$ through the designated three-cylinder tube. This will contain some additional short segments compared to our lower bound, namely, the segments connecting the endpoints of the geodesic ($f(x_i)$ and $f(x_j)$) to the entrance and exit of the tube. The total length of these segments is shown to be less than $\epsilon {\mathrm{dist}}_X(x_i,x_j)$. $◀$

We note the following observation from within the proof of Theorem 3 for later use.