I was just asked the following amusing question. Consider $\mathbb{R}^2$ with the taxicab metric (the taxicab distance between $(a,b)$ and $(c,d)$ is $|a-c|+|b-d|$). Given a finite set of points in $\mathbb{R}^2$ such that the taxicab distance between any two of them is at most $D$, is there a point in $\mathbb{R}^2$ which has taxicab distance at most $D/2$ from all of them?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Is the distance of the point we're looking for also measured in the taxicab metric? $\endgroup$Ben Grossmann– Ben Grossmann2020-01-12 18:38:46 +00:00Commented Jan 12, 2020 at 18:38
-
$\begingroup$ Is the point in question also in the finite set? $\endgroup$mephistolotl– mephistolotl2020-01-12 19:25:55 +00:00Commented Jan 12, 2020 at 19:25
-
$\begingroup$ Question edited to clarify. Yes, also taxicab metric, no the point doesn't have to be in the finite set. $\endgroup$Kevin Buzzard– Kevin Buzzard2020-01-12 19:47:58 +00:00Commented Jan 12, 2020 at 19:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Found a fun solution. First, note that this question is equivalent to the same question asked about the $ \mathcal{l}^\infty $ metric on $ \mathbb{R}^2 $ since $ (\mathbb{R}^2, \mathcal{l}^\infty) $ is isometric to $ (\mathbb{R}^2, \mathcal{l}^1) $ (the taxicab space).
In $ (\mathbb{R}^2, \mathcal{l}^\infty ) $ the argument is pretty easy to write down. If $ S $ is your subset of $ \mathbb{R}^2 $, define: $$ a = \inf_{(x,y)\in S}{x}, \ \ b = \sup_{(x,y)\in S}{x},\ \ c = \inf_{(x,y)\in S}{y},\ \ d = \sup_{(x,y)\in S}{y} $$ and take your central point $ p = (\frac{a+b}{2}, \frac{c+d}{2}) $.
-
$\begingroup$ Very nice! [filler] $\endgroup$Kevin Buzzard– Kevin Buzzard2020-01-15 11:07:10 +00:00Commented Jan 15, 2020 at 11:07