Total orders realizable as the distances between two sets of points
Let \(P= \{ p_0, p_1, \dots, p_{n-1}\}\) be a set of points in the \(d\)-dimensional Euclidean space \(\mathbb{R}^d\). Assume that the points are in general position, i.e. there are no \(d+1\) of them lying in the same hyperplane, and that all pairs of points are at different distances. Let \(\binom{[n]}{2}\) denote the set of ordered pairs \((i,j)\) with \(0 \leq i < j \leq n-1\). Order the elements of \(\binom{[n]}{2}\) by \((i,j) < (k,l)\) iff \(\|p_i-p_j\| < \|p_k-p_l\|\). An order on \(\binom{[n]}{2}\) is called \emph{realizable} in \(\mathbb{R}^d\) if there is some \(n\)-element set \(P\) in \(\mathbb{R}^d\) in general position that induces this order. The problem of finding the smallest dimension \(d\) such that every order on \(\binom{[n]}{2}\) is realizable in \(\mathbb{R}^d\) was introduced by \textit{V. H. Almendra-Hernández} and \textit{L. Martínez-Sandoval} [Comput. Geom. 107, Article ID 101898, 10 p. (2022; Zbl 1487.52010)]. In particular, they showed that every order on \(\binom{[n]}{2}\) is realizable in \(\mathbb{R}^{n-2}\), and gave an example which cannot be realized in \(\mathbb{R}^{n-3}\). In this paper, the authors show that this configuration can be realized in \(\mathbb{R}^{n-3}\), which leaves open the above question.\N\NSimilarly, if \(2 \leq n \leq m\) and \(d\) are positive integers and \(P= \{ p_0, p_1, \dots, p_{n-1}\}\) and \(Q= \{ q_0, q_1, \dots, q_{m-1}\}\) are sets of points in \(\mathbb{R}^d\) in general position and with pairwise distinct distances, an order can be defined on the set \([n] \times [m]\) of the ordered pairs \((i,j)\) with \(0 \leq i \leq n-1\) and \(0 \leq j \leq m-1\) by setting \((i,j) < (k,l)\) iff \(\|p_i-q_j\| < \|p_k - q_l\|\). An order on \([n] \times [m]\) is called \emph{realizable} in \(\mathbb{R}^d\) if there are point sets \(P\) and \(Q\) in \(\mathbb{R}^d\) which induce this order. In this paper the authors prove that the smallest value of \(d\) such that every order on \([n] \times [m]\) can be realized in \(\mathbb{R}^d\) is \(d=n\).
- Excursions into combinatorial geometry
- scientific article; zbMATH DE number 960150 (Why is no real title available?)
- On prescribing total orders and preorders to pairwise distances of points in Euclidean space
- Realizability of graphs and linkages
- The Erdős distance problem
- Two notions of unit distance graphs
This page was built for publication: Total orders realizable as the distances between two sets of points
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906690)
