On prescribing total preorders and linear orders to pairwise distances\n of points in Euclidean space

2021/11/16 by Víctor Hugo Almendra-Hernández, Almendra-Hernández, Víctor Hugo, Leonardo Martínez-Sandoval +1
Mathematics · #Point processes and geometric inequalities #Mathematical Approximation and Integration #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2111.08895

Abstract

We show that any total preorder on a set with binomn2 elements\ncoincides with the order on pairwise distances of some point collection of size\nn in \ℝ^n-1. For linear orders, a collection of n points in\n\ℝ^n-2 suffices. These bounds turn out to be optimal. We also find\nan optimal bound in a bipartite version for total preorders and a near-optimal\nbound for a bipartite version for linear orders. Our arguments include tools\nfrom convexity and positive semidefinite quadratic forms.\n

Related

• Total orders realizable as the distances between two sets of points
• Permutations of point sets in ℝ^d
• Ordering Candidates via Vantage Points
• Limits of Order Types
• On Locality-Sensitive Orderings and their Applications