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 p q . 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 3 ⌊ n / 2 ⌋, for every n > 2 . For d ⩾ 3, it follows from the Erdős–Stone theorem in extremal graph theory that N d ( n ) = 1 2 ( 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 ⌉ ⩽ k ( d ) ⩽ d ‐ 1 . Moreover, asymptotically we have lim n → ∞ k ( d ) / d = 1 . The same bounds hold for the maximum number of strict double‐normal pairs.