# Plotting the open ball for the post office metric space

The post office metric space, $P$ has the distance function defined as follows:

$$d_P (\mathbf{x},\mathbf{y}) := \begin{cases} 0 & \mathbf{x} = \mathbf{y}\\ \Vert \mathbf{x}\Vert_2+\Vert \mathbf{y}\Vert_2 & \mathbf{x}\neq \mathbf{y} \end{cases}$$

where $\Vert \mathbf{x}\Vert_2 = \sqrt{x_1^2+x_2^2}$ is the Euclidean distance from $\mathbf{x}=(x1,x2) \in \mathbb{R}^2$ to the origin.

I am interested in drawing the balls of this metric centered at point $\mathbf{p}$, having a radius $r$:

$$B_r(\mathbf{p}) \triangleq \{\mathbf{x} \in P\vert\ d(\mathbf{x},\mathbf{p})<r \}$$

Does anyone have any tips on how to do this?

-

## migrated from stackoverflow.comMar 23 '12 at 20:32

This question came from our site for professional and enthusiast programmers.

I'll just post because I don't think Eli Lansey’s answer uses the right definition for post office metric. I like the other name of the post office metric better: British rail metric. It assumes that, when going from point A to point B, the fastest path is to go via London (i.e., the origin), unless of course you're already at your destination!

So, we consider a fixed point $\mathbf{p}$, the ball $B_r(\mathbf{p})$ is the set of points $\mathbf{q}$ that satisfy:

$$\|\mathbf{p}\|^2 + \|\mathbf{q}\|^2 < r^2$$

that is, if we have $\mathbf{q}=(x,y)$, the ball $B_r(\mathbf{p})$ is the union of the $\{\mathbf{p}\}$ and all points satisfying:

$$x^2 + y^2 < r^2 - \|\mathbf{p}\|^2$$

The latter is the ball of radius $r' = \sqrt{r^2 - \|\mathbf{p}\|^2}$ around the origin for the Euclidean distance in the plane, which we might note $B_{r'}^{\text{E}}(\mathbf{O})$. To summarize:

• if $r < \|\mathbf{p}\|$, $B_r(\mathbf{p}) = \{\mathbf{p}\}$
• otherwise, $B_r(\mathbf{p}) = \{\mathbf{p}\} \cup B_{r'}^{\text{E}}(\mathbf{O})$ with $r' = \sqrt{r^2 - \|\mathbf{p}\|^2}$

Okay, this being Mathematica.SE, I figure I could give code to draw the above, in addition to doing the maths. So, this draws the ball (point $\mathbf p$, which is part of the ball, is drawn as a little filled square so it's visible):

ball[p_, r_] := Show[
RegionPlot[
x^2 + y^2 + p[[1]]^2 + p[[2]]^2 < r^2, {x, -5, 5}, {y, -5, 5},
PerformanceGoal -> "Quality"],
Graphics[{Blue, Point[p]}]
]


and this is an animation of a ball of radius 3 as its center $\mathbf p$ moves from $(0,0)$ to $(0,4)$:

-

Here's my attempt at visualizing this using Manipulate.

postOffice[a_, b_] := If[a == b, 0, Norm[a] + Norm[b]]

Manipulate[
Grid[{{
ContourPlot[postOffice[{x, y}, p], {x, -5, 5}, {y, -5, 5},
ImageSize -> 360, ColorFunctionScaling -> False,
ColorFunction -> (ColorData["Rainbow", Rescale[#, {0, 2 Norm[{5, 5}]}]]&),
Epilog -> {ColorData["Rainbow", 0], Point[p]}, PerformanceGoal -> "Quality"],
DensityPlot[y, {x, -.5, .5}, {y, 0, 2 Norm[{5, 5}]},
AspectRatio -> Automatic, ColorFunctionScaling -> False,
ColorFunction -> (ColorData["Rainbow", Rescale[#, {0, 2 Norm[{5, 5}]}]]&),
FrameTicks -> {{None, All}, {None, None}}, PlotRangePadding -> None]
}}],
{{p, {0, 0}}, {-5, -5}, {5, 5}, ControlType -> Locator}]


Notes:

• the distance between the locator and another point in the scene is represented by the color of the plot, as well as by the automatic tooltips on the contours

• the color function is done on a global scale, with the values being manually scaled.

• there is a small purple point under the locator, since the distance from a point to itself is zero.

-
dP[x_, y_] := Piecewise[{{0, x == y}, {Abs[x] + Abs[y], y != x}}]

While I think this is correct for two points x,y in R, in R^2 you need to use Norm instead of Abs. (And it then gets trickier to visualize, since it's a function of two points.) –  Brett Champion Mar 23 '12 at 21:23