12

I want to construct a point set where each point has the same (w.l.o.g., unit) distance to all other points in the $L_1$ metric. Example: The points $\left(\frac{1}{2},0\right)$, $\left(-\frac{1}{2},0\right)$, $\left(0,\frac{1}{2}\right)$ and $\left(0,-\frac{1}{2}\right)$ have unit distance between each other. Similarly, it is possible to embed six points into $\mathbb{R}^3$, eight points into $\mathbb{R}^4$, etc..

Question: Is this the most efficient layout, or is it possible to e.g. embed eight ($=2^3$) points into $\mathbb{R}^3$, or 16 points into $\mathbb{R}^4$?

Notes: The metric is fixed, I'm only free to move the points. (I could use another metric for the problem; however, for instance, in $L_2$ it isn't even possible to embed four points as required.)

Perhaps related:

Is there any object/metric within all points are at same distance to each other?

Existance and uniqueness of solution for a point with fixed distances to three other points

Community
  • 1
krlmlr
  • 630
  • (For the euclidian metric, the maximum is $n+1$ points in ${\mathbb R}^n$: http://math.stackexchange.com/questions/1470494/does-anyone-know-if-it-has-been-proved-what-the-maximum-number-of-points-in-n.) – Martin R Feb 13 '16 at 19:41
  • Your claim is erroneous. Draw the picture and measure all possible distances - 6 of them. – Moti May 21 '20 at 19:38
  • @Moti: Whose claim? Which claim? – krlmlr May 22 '20 at 08:36
  • The claim that EACH point has equal distance from all others. In 2D you can have only up to 3. In 3D up to 4... in your example this is not true. – Moti May 22 '20 at 16:58
  • 1
    @Moti: I agree if we assume the Euclidean metric. This question is about the $L_1$ metric, Manhattan distance. – krlmlr May 22 '20 at 19:46
  • https://math.stackexchange.com/a/4746863/965410 This related post was updated with an answer. If anyone is comes across this post It may help. – Jordan T Aug 03 '23 at 14:35

0 Answers0