Discrete and lexicographic Helly-type theorems
type: Item
instance of: scholarly article
title: Discrete and lexicographic Helly-type theorems
zbMATH Open document ID: 1157.52006
author: Nir Halman
published in: Discrete \& Computational Geometry
publication date: 2008-08-19T00:00:00Z
review text: Helly's theorem says that if every \(d+1\) elements of a given finite family of convex sets in \(\mathbb{R}^{d}\) have a common point, then there is a point common to all sets of the family. The author defines three new types of Helly theorems: ``discrete'' Helly theorems -- where the common point should belong to an a-priori given set, lexicographic Helly theorems -- where the common point should not be lexicographically greater than a given point, and lexicographic-discrete Helly theorems. A typical example of a discrete Helly theorem is the following theorem due to \textit{J.-P. Doignon} [J. Geometry 3, 71--85 (1973; Zbl 0245.52004)]: ``Let \(H\) be a finite family of at least \(2^{d}\) convex sets in \(\mathbb{R}^{d}\). If every \(2^{d}\) or fewer members of \(H\) have a common point with integer coordinates, then there is a point with integer coordinates common to all members of \(H\).'' The author discusses and proves a series of theorems of the above mentioned types, including piercing and transversal problems.
reviewed by: Johann Linhart
Mathematics Subject Classification ID: 52A35
zbMATH DE Number: 5313107
zbMATH Keywords: Helly theorems
zbMATH Keywords: piercing problems
zbMATH Keywords: line transversals
MaRDI profile type: Publication
full work available at URL: s00454-007-9028-8
OpenAlex ID: W2004730424
cites work: Helly-type theorems and generalized linear programming
cites work: Über ein Problem aus der kombinatorischen Geometrie
cites work: Intersection properties of boxes in \(R^ n\).
cites work: Q5341481
cites work: Convexity in cristallographical lattices
cites work: Q3772828
cites work: Q3138749
cites work: On a theorem of L. A. Santaló
cites work: On common transversals
cites work: Q3249399
cites work: On the Algorithmic Aspects of Discrete and Lexicographic Helly-Type Theorems and the Discrete LP-Type Model
cites work: Ausgewählte Einzelprobleme der kombinatorischen Geometrie in der Ebene
cites work: Common Secants for Plane Convex Sets
cites work: Q4530626
cites work: Proof of Grünbaum's conjecture on common transversals for translates
cites work: Q4011327
cites work: A generalization of Hadwiger's transversal theorem to intersecting sets
DOI: 10.1007/S00454-007-9028-8
Recommended article: On the Algorithmic Aspects of Discrete and Lexicographic Helly-Type Theorems and the Discrete LP-Type Model
Recommended article: Q4514307
Recommended article: A discrete variant of Farkas' lemma and related results
Recommended article: Discrete Reifenberg-type theorem
Recommended article: Q6072493
Recommended article: Discrete quantitative Helly-type theorems with boxes
Recommended article: A discrete variant of Farkas' lemma
Recommended article: The Discrete Analog of the Malgrange–Ehrenpreis Theorem
Recommended article: A discrete version of the Mishou theorem
Recommended article: On a discrete version of the Laugesen-Morpurgo conjecture
description: scientific article; zbMATH DE number 5313107