Halving point sets

DOI10.4171/DMS/1-3/46MaRDI QIDQ1126842zbMATH OpenFDO

Authors Artur Andrzejak, Emo Welzl

Publication date 5 August 1998

Published in Documenta Mathematica (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/230400, http://www.emis.de/journals/DMJDMV/xvol-icm/14/Welzl.MAN.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(j\)-facets\(k\)-levels\(k\)-setscomputational geometry

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational aspects related to convexity (52B55) Erd?s problems and related topics of discrete geometry (52C10) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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.

Recommendations

• Point sets with many \(k\)-sets
• On the number of halving planes
• Cutting dense point sets in half

Cited in

(16)

• Points and triangles in the plane and halving planes in space
• Cutting dense point sets in half
• On the number of corner cuts
• Dense point sets with many halving lines
• On halving-edges graphs
• On the number of halving planes
• Few cuts meet many point sets
• Crossing numbers of imbalanced graphs
• scientific article; zbMATH DE number 1802825 (Why is no real title available?)
• scientific article; zbMATH DE number 5122066 (Why is no real title available?)
• An improved, simple construction of many halving edges
• k-sets and k-facets
• Halfway Points
• Halving lines and measure concentration in the plane
• Entering and leaving \(j\)-facets
• Point sets with many \(k\)-sets

This page was built for publication: Halving point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126842)