Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T21:48:43.376Z Has data issue: false hasContentIssue false

DOUBLE-NORMAL PAIRS IN SPACE

Published online by Cambridge University Press:  14 August 2014

János Pach
Affiliation:
EPFL Lausanne, Switzerland Rényi Institute, Budapest, Hungary email pach@cims.nyu.edu
Konrad J. Swanepoel
Affiliation:
Department of Mathematics, London School of Economics and Political Science, Houghton Street, London WC2A 2AE, U.K. email k.swanepoel@lse.ac.uk

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A double-normal pair of a finite set $S$ of points that spans $\mathbb{R}^{d}$ is a pair of points $\{\mathbf{p},\mathbf{q}\}$ from $S$ such that $S$ lies in the closed strip bounded by the hyperplanes through $\mathbf{p}$ and $\mathbf{q}$ perpendicular to $\mathbf{p}\mathbf{q}$. A double-normal pair $\{\mathbf{p},\mathbf{q}\}$ is strict if$S\setminus \{\mathbf{p},\mathbf{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 $\mathbb{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\lfloor n/2\rfloor$, for every $n>2$. For $d\geqslant 3$, it follows from the Erdős–Stone theorem in extremal graph theory that $N_{d}(n)=\frac{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, $\lceil d/2\rceil \leqslant k(d)\leqslant d-1$. Moreover, asymptotically we have $\lim _{n\rightarrow \infty }k(d)/d=1$. The same bounds hold for the maximum number of strict double-normal pairs.

Information

Type
Research Article
Copyright
Copyright © University College London 2014