DOUBLE-NORMAL PAIRS IN SPACE. Issue 1 (14th August 2014) - Pach, János; Swanepoel, Konrad J.
Abstract: A double-normal pair of a finite set S of points that spans R^d is a pair of points {p, q} from S such that S lies in the closed strip bounded by the hyperplanes through p and q perpendicular to pq . A double-normal pair {p, q} is strict if S{p, q} lies in the open strip. The problem of estimating the maximum number N_d(n) of double-normal pairs in a set of n points in R^d, was initiated by Martini and Soltan [ Discrete Math. 290 (2005), 221–228]. It was shown in a companion paper that in the plane, this maximum is 3n/2 floor, for every n>2 . For d3, it follows from the Erdős–Stone theorem in extremal graph theory that N_d(n)=12(1-1/k)n^2+o(n^2) for a suitable positive integer k=k(d) . Here we prove that k(3)=2 and, in general, d/2 ceil k(d)d-1 . Moreover, asymptotically we have _n→ ∞ k(d)/d=1 . The same bounds hold for the maximum number of strict double-normal pairs.