DOUBLE‐NORMAL PAIRS IN SPACE. Issue 1 (14th August 2014)

• Record Type: Journal Article
• Authors: Pach, János; Swanepoel, Konrad J.
• Is Part Of: Mathematika. Volume 61:Issue 1(2015)
• Page Start: 259
• Page End: 272
• Publication Date: 2014-08-14
• Subjects: 52C10 (primary); Mathematics -- Periodicals; 510.5
• DOI: 10.1112/S0025579314000217
• Languages: English
• ISSNs: 0025-5793

Abstract

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.