Permutations of point sets in ℝ^d

2021/06/27 by Alvaro Carbonero, Beth Anne Castellano, Carbonero, Alvaro +8
Computer Science · Mathematics · #05A05 #52C10 primary #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG)

paper · pdf · doi:10.48550/arxiv.2106.14140

openalex publication_date 2021/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a set S consisting of n points in ℝ^d and one or two vantage points, we study the number of orderings of S induced by measuring the distance (for one vantage point) or the average distance (for two vantage points) from the vantage point(s) to the points of S as the vantage points move through ℝ^d. With one vantage point, a theorem of Good and Tideman \citeMR505547 shows the maximum number of orderings is a sum of unsigned Stirling numbers of the first kind. We show that the minimum value in all dimensions is 2n-2, achieved by n equally spaced points on a line. We investigate special configurations that achieve intermediate numbers of orderings in the one--dimensional and two--dimensional cases. We also treat the case when the points are on the sphere S², connecting spherical and planar configurations. We briefly consider an application using weights suggested by an application to social choice theory. We conclude with several open problems that we believe deserve further study.

Related

• Bounds on point configurations determined by distances and dot products
• Ordering Candidates via Vantage Points
• Lattice Configurations Determining Few Distances
• Planar point sets with forbidden 4-point patterns and few distinct distances
• A protrusive ordering of 5 points not witnessed by any finite multiset