4
$\begingroup$

Two closed balls with a common radius are positioned so that the centre of either ball is on the boundary of the other. I am interested in the extremal diameter of their intersection, in an arbitrary metric space.

To formalise this, let $X$ be a metric space with at least two points. Let $d(x,y)$ denote the distance between points $x$ and $y$, and let $d_{x,y}$ denote the diameter of the intersection of the two balls with centres $x$ and $y$, both having radius $d(x,y)$.

The triangle inequality implies that $d_{x,y} \le 2d(x,y)$. If $x$ and $y$ are distinct, then $d(x,y) > 0$, so in this case we can define $q_{x,y} = \frac{d_{x,y}}{d(x,y)}$. Now let $q_X = \sup \{q_{x,y} \mid x, y \in X, x \ne y\}$ be the "diameter bound" for $X$. We then have $q_X \le 2$, for any metric space $X$ with at least two points.

This "diameter bound" can be improved for some metric spaces:

  1. $q_X = 1$ for the discrete space in which distances are all either 0 or 1.

  2. $q_X = 1$ also for the case of a Euclidean space of dimension 1.

  3. For Euclidean spaces of dimension 2 or 3, $q_X \le \sqrt{3} \approx 1.73$.

More generally, for $\mathbb{R}^n$ this seems to be a kind of converse of Jung's Theorem, but it is not clear to me whether that result can be applied directly in the setting envisaged here.

One can then try to prove such upper bounds for one's favourite metric spaces. For instance, one can show that for tree metrics $q_X = 1$, and that in "nice" $\delta$-hyperbolic spaces one can get arbitrarily close to 1 (as the parameter $\delta$ determines ):

  • Victor Chepoi, Feodor F. Dragan, Bertrand Estellon, Michel Habib, Yann Vaxès. Notes on diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs, Electronic Notes in Discrete Mathematics 31, 231–234, 2008. doi:10.1016/j.endm.2008.06.046

Instead of this kind of case-by-case taxonomy of metric spaces, I'm interested in the following general question.

Is there a result that ties together the upper bound on $q_X$ with properties of the metric space $X$?

(This question is abstracted from an algorithmic question in data mining.)

$\endgroup$
  • 2
    $\begingroup$ Two minor remarks: 1) $q_X = 1$ also for ultrametric spaces. 2) I assume by a Euclidean space of dimension $n$ you mean a set $X \subset \mathbb{R}^n$. If so your bound of $\sqrt{3}$ holds for any dimension $n \ge 2$. $\endgroup$ – Mark Meckes Oct 24 '18 at 16:57
6
$\begingroup$

The best result that I know is that when $X$ simply-connected manifold with non-positive sectional curvature ($n \geq 2$), $q_X = \sqrt{3}$. This directly follows from a corollary of the Rauch comparison theorem. For a reference, see Corollary 2.1 of these lecture notes 1.

To explain why this is the best that I was able to do, let me construct two examples where $q_X \approx 2$, and explain what I need to assume to rule these out. There seems to be two obstacles to bounding $q_X$. One of these is controlled by the global topology and the other is controlled by the more local geometry.

For an example in which $q_X$ can be 2 by the global topology, consider a graph on 4 vertices (say $(v_1, v_2,v_3,v_4)$ which is complete except for a single edge missing (say between $v_2$ and $v_4$). Put the standard metric on this graph assuming all the edges have length 1. Then the intersection of the balls of radius 1 centered on $v_1$ and $v_3$ is the vertices $v_2$ and $v_4$, as well as the entire edge connecting $v_1$ and $v_3$. This set has diameter 2, because the distance from $v_2$ to $v_4$ is 2. For a picture of such a graph, see the edit below. It's also possible to thicken up this graph and make it into a smooth manifold. Here, the space is not simply connected, and that's allowing us to take alternate paths to points. There is no homotopy between these paths giving "in-between" paths, so $q_X$ is large.

However, there is another obstruction. Even if the space is simply connected and smooth, we may still have $q_X > 2 - \epsilon$. For an example of this, consider the surface given by the graph of $$ f(x,y) = 20 e^{-((x+2)^2+y^2)} + 20 e^{-((x-2)^2+y^2)}.$$ with the metric from embedding it in $\mathbb{R}^3$. For an intuitive picture, this looks like a mostly flat world with two towering mountains on it. If I consider the points $p =(0,-2)$ and $ q =(0,2)$, then the intersection of the balls of radius just slightly larger than $\sqrt{29}$ contains the points $(-5,0)$ and $(5,0)$. However, in this world, the shortest path from $(-5,0)$ to $(5,0)$ should go around the mountain, so is close to $2\sqrt{29}$ in length. What's going on is that people living at $p$ can use the valley between the mountains to travel to $q$, so the two points are relatively close. In many ways, this closely resembles the earlier example with the graph. It is now possible to what were formerly the loops on the graph, but it is now very costly to do so.

These two examples demonstrate that we can only hope to prove upper bound on $q_X$ when $X$ is simply-connected (or perhaps $1$-connected). Otherwise there will probably be counterexamples no matter how nice the geometry looks. To rule out our mountain example, the issue is fundamentally the curvature of the space. It turns out that if the curvature is positive, one can always create examples that resemble this example, so this suggests that we need to consider non-positive curvature.

If we assume non-positive curvature, we can use triangle comparison theorems to rule out such examples. In particular, on a simply-connected manifold of non-positive sectional curvature, the Rauch comparison theorem implies that $q_X \leq \sqrt{3}$. Using small triangles, we can get arbitrarily close to $\sqrt{3}$, so this implies that $q_X = \sqrt{3}$. In strictly negatively curved space, as $d(x,y)$ grows, one gets an upper bound on $q_{x,y}$ converging to 1.

There may be more that can be said. In all the examples I found with positive curvature that had $q_X$ large, I needed the diameter of the space to be sufficiently large so as to fit two mountains. Perhaps if the curvature is allowed to be positive (but bounded), and the diameter is sufficiently small, one can again obtain an upper bound on $q_X$. I'm not sure how to do this though.

$\textbf{Edit:}$

I wanted to include some pictures to help with the intuition. The first is a picture of the graph for the first example. This graphic was provided by Matt F., so all credit for producing it goes to him.

$${\Huge \nabla \! \! \! \! \! \! \! \Delta }$$

If one takes a tubular neighborhood around this graph (as if were made from PVC piping), then it's possible to construct a smooth genus 2 surface with $q_X > 2 - \epsilon$.

For the second example, here is a plot of the function, which shows the two mountains and the valley between them.

Here is a plot of f(x,y)

If you would rather manipulate the picture yourself, you can run the following line in Mathematica or on Wolfram cloud.

Plot3D[ 20*Exp[-((x - 2)^2 + y^2)] + 20*Exp[-((x + 2)^2 + y^2)], {x, -10, 10}, {y, -10, 10}, PlotRange -> All]

$\endgroup$
  • 1
    $\begingroup$ It seems you wanted to say Toponogov comparison (not Rauch comparison). $\endgroup$ – Anton Petrunin Oct 25 '18 at 0:53
  • $\begingroup$ Bit more generally, CAT(0) implies $q\le \sqrt{3}$, I would not be surprized if $q\le \sqrt{3}$ is equivalent to CAT(0) for length spaces. $\endgroup$ – Anton Petrunin Oct 25 '18 at 0:59
  • 1
    $\begingroup$ You are right, I called Toponogov by analogy. $\endgroup$ – Anton Petrunin Oct 25 '18 at 1:25
  • 2
    $\begingroup$ $\nabla \! \! \Delta$ $\endgroup$ – Matt F. Oct 25 '18 at 2:32
  • 1
    $\begingroup$ This is exactly CAT(0) condition --- it is global and it implies simply-connectedness. $\endgroup$ – Anton Petrunin Oct 25 '18 at 3:18
4
$\begingroup$

Sorry, this is only a comment.

It looks to me as though your question may have something to do with the $CAT(\kappa)$ property. I have not checked any details, but maybe one could say something like: in a $CAT(\kappa)$ space, $q_X$ is bounded by its value in the model space of constant curvature $\kappa$.

Your definition can be rephrased as follows: Consider all ordered quadruples $(x_1,x_2,x_3,x_4)$ in your space in which all cyclically consecutive distances $d(x_i,x_{i+1})$ are bounded by $d(x_1,x_3)$. Then $q_X$ is the supremum of $d(x_2,x_4)/d(x_1,x_3)$ over such quadruples.

This looks pretty close to the discussion in section 2.1 of https://arxiv.org/pdf/1701.03483.pdf

I'm sure others with more expertise can say more.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.