Halving point sets
type: Item
instance of: scholarly article
title: Halving point sets
zbMATH Open document ID: 0911.52010
author: Artur Andrzejak
author: Emo Welzl
published in: Documenta Mathematica
publication date: 1998-08-05T00:00:00Z
full work available at URL: https://eudml.org/doc/230400
full work available at URL: Welzl.MAN.html
review text: Given \(n\) points in \(\mathbb R^d\), a hyperplane is called halving if it has at most \(\lfloor n/2 \rfloor\) points on either side. This paper surveys known results about the question: How many partitions of a point set (into the points on one side, on the hyperplane, and on the other side) by halving hyperplanes can be realized by an \(n\)-point set in \(R^d\)? This is a special case of the famous \(k\)-set problem. For the planar case the authors discuss the recent upper bound due to \textit{T. Dey} [Discrete Comput. Geom. 19, No. 3, 373-382 (1998; Zbl 0899.68107)] and described the Lovász crossing lemma, a useful result in this topic. The remainder of the paper states the known bounds on the number of \(j\)-facets and presents connections to other topics in discrete geometry and algorithms. These include the upper bound theorem, \(k\)-levels and parametric matroid optimization.
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 52B05
Mathematics Subject Classification ID: 52B55
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 1184385
zbMATH Keywords: computational geometry
zbMATH Keywords: \(k\)-sets
zbMATH Keywords: \(k\)-levels
zbMATH Keywords: \(j\)-facets
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1184385