On prescribing total orders and preorders to pairwise distances of points in Euclidean space. (English) Zbl 1487.52010

Almendra-Hernández, Víctor Hugo; Martínez-Sandoval, Leonardo

Comput. Geom. 107, Article ID 101898, 10 p. (2022).

Summary: We show that any total preorder on a set of the form \(\begin{pmatrix} X \\ 2 \end{pmatrix}\) where \(X\) has \(n\) elements coincides with the order on pairwise distances of some point collection of size \(n\) in \(\mathbb{R}^{n-1}\). For total orders, a collection of \(n\) points in \(\mathbb{R}^{n-2}\) suffices. These bounds turn out to be optimal. We also find an optimal bound in a bipartite version for total preorders and a near-optimal bound for a bipartite version for total orders. Our arguments include tools from convexity and positive semidefinite quadratic forms.

MSC:

52A37

Other problems of combinatorial convexity

Keywords:

Euclidean distances; total orders; total preorders; convex sets

References:

[1]	Erdös, P., On sets of distances of n points, Am. Math. Mon., 53, 5, 248-250 (1946) · Zbl 0060.34805
[2]	Yugai, S., On the largest number of diameters of a point set in Euclidean space, (Investigations in Topological and Generalized Spaces (1988)), 84-87, (in Russian) · Zbl 0734.52005
[3]	Martini, H.; Soltan, V., Antipodality properties of finite sets in Euclidean space, Discrete Math., 290, 2, 221-228 (2005) · Zbl 1066.52010
[4]	Schoenberg, I., Remarks to Maurice Fréchet’s article ‘Sur la definition axiomatique d’une classe d’espace distances vectoriellement applicable sur l’espace de Hilbert’, Ann. Math., 36, 3, 724-732 (1935) · JFM 61.0435.04
[5]	Matoušek, J., Thirty-Three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra (2010), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 1195.00043
[6]	Dekster, B.; Wilker, J., Edge lengths guaranteed to form a simplex, Arch. Math., 49, 351-366 (1987) · Zbl 0608.52007