We place three non-overlapping, noncollinear points on an arbitrarily large grid graph (not worrying about infinities). Call these points $(p_1,p_2,p_3)$. Assuming taxicab geometry, is it possible for there to exist two or more points on the lattice, $(p_a,p_b)$, that have the same ordered set of distances to $(p_1,p_2,p_3)$? Does this hold true for a $d$-dimensional grid graph if we ask for an ordered set of distances to $d+1$ non-overlapping and noncollinear points (trivially true for $d = 1$)?

Please notice that I specify the distances to each point should be an ordered set. In other words, if your set of distances to $(p_1,p_2,p_3)$ is $(d_1, d_2, d_3)$, this set of distances is distinct from, for example, $(d_2, d_1, d_3)$.

In response to coffeemath's answer: The example you give (scaled by a factor of 20), yields $(p_1,p_2,p_3) = ((0,0),(-20,20),(10,10))$ and $(p_a,p_b) = ((-5,15),(-4,16))$. In taxicab geometry, we thus have $(d_1, d_2, d_3) = (20,20,20)$ for both $p_a$ and $p_b$. However, in Euclidean geometry, we have that $(d_1, d_2, d_3) = (5*10^{\frac{1}{2}},5*10^{\frac{1}{2}},5*10^{\frac{1}{2}})$ for $p_a$ and $(d_1, d_2, d_3) = (4*17^{\frac{1}{2}},4*17^{\frac{1}{2}},2*58^{\frac{1}{2}})$ for $p_b$. So the answer to my question is "no", a particular instance of the ordered set $(d_2, d_1, d_3)$ can exist for multiple lattice points.

Followup question (while my account details are being sorted out) - Are there any simple constraints that would make my statement true? What if we have $d+2$ points for a $d$-dimensional grid graph and ask about the uniqueness of an ordered set of these points? What if we consider a hexagonal lattice version of taxicab geometry?

Note to CoffeeMath: Still haven't been able to fuse my account with this one, but to respond:

"...maybe the requirement should be that the n+1 points not all lie on any hyperplane (on the analogy of for 2-space requiring no three on a line (hyperplane in two space)? For highjer dimensions I think "no three on a line" might be too easy."

Right, I think this is a very natural extension to the "non collinear" constraint I imposed in 2D. In general, we want to break any "trivial" axes of symmetry. In the continuum limit, we might call this randomly perturbing the vertices of the grid graph in $R^d$. Also, as a quick note, I never meant that additional dimensions would somehow constrain lower-dimensional embeddings of graphs.

  • $\begingroup$ I think if you imagine a "disk" of "radius" $r$ centered at a point $P$ in taxicab geometry, you get (in the 2-d case) a square tilted at 45 degrees centered at $P$ with equation $d^*(P-X)=r$ with $d^*$ the taxicab metric. If several of these tilted squares share a nontrivial convex set in their common boundary (which can occur), then any number of points could be found which lie in that common part, thus all having the same ordered $n$ tuples of distances from the centers. I believe a similar thing happens in higher dimensions. $\endgroup$ – coffeemath Apr 18 '13 at 13:45
  • $\begingroup$ Have a look at the question I added to the end of my answer: I'm wondering about proper dimension requirements... $\endgroup$ – coffeemath Apr 18 '13 at 20:21
  • $\begingroup$ Latest add-on to my answer: an example in dimension $n$. $\endgroup$ – coffeemath Apr 19 '13 at 21:26

A 2-d example: $p_1=(0,0),\ p_2=(-1,1),\ p_3=(1/2,1/2).$ Note these are noncollinear and distinct ("nonoverlapping").

Now let $p_a=(-1/4,3/4),\ p_b=(-1/5,4/5).$

Then for each of $p_a,p_b$ the sequence of taxicab distances to $p_1,p_2,p_3$ is $(1,1,1).$

If you seek only integer coordinates (as some mean by "lattice"), this example can be scaled on multiplying all coordinates by $20$.

An example in $\mathbb{R}^n$

Define the following three sets, where all summations are from $1$ to $n$.

$A:\ \sum x_i=1,\ [0 \le x_i \le 2n]$

$M:\ \sum x_i=3n^2,\ [2n \le x_i \le 4n]$

$B:\ \sum x_i=6n^2-1,\ [4n \le x_i \le 6n].$

Note that there is room in any of these sets for infinitely many points, e.g. for $M$ we have from $2n \le x_i \le 4n$ on summing from $1$ to $n$ that $2n^2 \le \sum x_i \le 4n^2$, giving plenty of "wiggle room" to select sums with total $3n^2$.

Now we select a specific set of $n+1$ points $p_k$. For $1 \le k \le n$ we let $p_k$ be the unit vector along the $k$th axis, i.e. $p_k$ has a $1$ as $k$th coordinate, others $0$. Note that there is only one hyperplane simultaneously containing every $p_k$ for $1 \le k \le n$. (This is $\sum x_i=1$.) For $p_{n+1}$ we select the point all of whose coordinates are $6n-1/n$, so that in fact $p_n$ lies in set $B$ at its "center", as it were.

Now it is easy to check the following statement, where $d$ denotes the taxicab distance: $$d(A,M)=d(M,B)=3n^2-1.$$ Here the use of the capital letters means we may take any points $a,m,b$ in the corresponding sets and have the equality of taxicab distances.

Finally consider the set $p_1,p_2,...,p_{n+1}$ of values of $p$. they are certainly all distinct by construction, and we claim as well they do not lie on any hyperplane. This is because the first $n$ of these points lie as a whole only on the hyperplane $\sum x_i=1$, and yet the final point $p_{n+1}$ does not lie on it.

And the "nonuniqueness" of the ordered sequences of distances is because any two (of the infinitely many) points in $M$ have all their taxicab distances to the $n+1$ points $p_k$ equal to $3n^2-1.$


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.