The number of extreme triples of a planar point set
type: Item
instance of: scholarly article
title: The number of extreme triples of a planar point set
zbMATH Open document ID: 0864.68109
DOI: 10.1007/BF02711130
published in: Discrete \& Computational Geometry
publication date: 1996-10-22T00:00:00Z
review text: Let \(S\) be a set of \(n\) points in \(\mathbb{R}^2\). For a half-plane \(h\), \(S'=S\cap h\) is called a \(k\)-set of \(S\) where \(k=|S'|\). Let \(e_k(S)\) denote the number of \(k\)-sets realized by \(S\), and define \(e_k(n)=\max\{e_k(S):S\subseteq\mathbb{R}^2,|S|=n\}\) for \(1\leq k\leq n-1\). 2-sets and 3-sets are called extreme pairs and extreme triples respectively. It is known that \(e_2(n)=\lfloor 3n/2\rfloor\) for \(n\geq 4\), and that \(e_3(n)\geq\lfloor 11n/6\rfloor\) for \(n\geq 15\), \(n\neq 19\). This note establishes the upper bound \(e_3(n)\leq\lfloor 11n/6\rfloor+1\) for \(n\geq 10\). This bound is established in a more general setting where the straight lines which determine the half-planes used in the definition are replaced by pseudolines, topological lines for which every pair intersect exactly once at a crossing point. The proof, by induction, is a somewhat tedious case analysis which establishes that maximal configurations (with respect to the number of extreme triples) can be made smaller by utilizing a suite of reduction techniques. The techniques of this approach are also used to provide a new proof of the \(e_2(n)\) result.
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 05B30
Mathematics Subject Classification ID: 05B25
zbMATH DE Number: 919853
zbMATH Keywords: pseudolines
author: Edgar A. Ramos
reviewed by: William E. Cherowitzo
MaRDI profile type: Publication
cites work: Q3772828
cites work: The number of extreme pairs of finite point-sets in Euclidean spaces
cites work: Proof of a conjecture of Burr, Grünbaum, and Sloane
cites work: Q3138746
cites work: Q4011326
full work available at URL: https://doi.org/10.1007/bf02711130
OpenAlex ID: W1995376955
description: scientific article; zbMATH DE number 919853