Furthest neighbours in space
type: Item
instance of: scholarly article
title: Furthest neighbours in space
zbMATH Open document ID: 0852.52008
DOI: 10.1016/0012-365X(95)00177-X
author: György Csizmadia
published in: Discrete Mathematics
publication date: 1996-07-02T00:00:00Z
review text: Let \(X = \{x_1, \dots, x_n\}\) be a set of \(n\) points in Euclidean 3-space \(\mathbb{R}^3\). For \(x_i \in X\), let \(f(x_i)\) denote the number of points in \(X\) at maximal distance from \(x_i\) (``furthest neighbours of \(x_i\)''). In 1988, D. Avis, P. Erdös and J. Pach proved that \[ d(n) : = \max_H \bigl\{ f(x_1) + \cdots + f(x_n) \bigr\} - n^2/4 - 3n/2 \leq c \] for a suitable real constant \(c\). The author sharpens this result by proving the Theorem: Suppose \(n > n_0\) \((n\) sufficiently large), then: (a) if \(n \equiv 0 \bmod 2\) then \(d(n) = 3\); (b) if \(n \equiv 1 \bmod 4\) then \(d(n) = 9/4\); (c) if \(n \equiv 3 \mod 4\) then \(d(n) = 13/4\). Besides he proves that if \(n\) points in \(\mathbb{R}^3\) determine the maximum number of furthest neighbours then they form a ``suspension'', i.e. a finite subset of the union of the polar axis and the equator of a sphere; the optimal arrangement is also given.
Mathematics Subject Classification ID: 52C10
zbMATH DE Number: 895989
zbMATH Keywords: suspension
zbMATH Keywords: furthest neighbours
MaRDI profile type: Publication
cites work: The Number of Furthest Neighbour Pairs of a Finite Planar Set
cites work: Repeated distances in space
cites work: Sphere-and-point incidence relations in high dimensions with applications to unit distances and furthest-neighbor pairs
cites work: Combinatorial complexity bounds for arrangements of curves and spheres
cites work: On the Number of Furthest Neighbour Pairs in a Point Set
cites work: On Sets of Distances of n Points
cites work: Q3270291
full work available at URL: 0012-365x(95)00177-x
OpenAlex ID: W2081284227
description: scientific article; zbMATH DE number 895989