Allowable interval sequences and separating convex sets in the plane
type: Item
instance of: scholarly article
title: Allowable interval sequences and separating convex sets in the plane
zbMATH Open document ID: 1246.52002
author: Mordechai Novick
published in: Discrete \& Computational Geometry
publication date: 2012-03-01T00:00:00Z
review text: In [Math. Scand. 45, 255--260 (1979; Zbl 0421.52004)], \textit{H. Tverberg} studied, for any given natural numbers \(r,k\), the existence of the smallest number of pairwise disjoint \(d\)-dimensional convex sets such that there is a closed half-space containing at least \(r\) of the sets, while the complementary closed half-space contains at least \(k\) of the remaining sets (this is usually called the \textit{(\(r,k\))-separation problem}). In the paper under review the author considers the case \(r=1\) in the plane and, denoting by \(f_k\) the above defined number, he improves previously known bounds by showing that \(f_k\leq \left\lceil(4+\sqrt{10})(k-1)-(3+\sqrt{10})/2\right\rceil\). In order to prove this result he applies the method of the so-called \textit{allowable interval sequences}, a kind of combinatorial object encoding properties of a family of pairwise disjoint planar convex sets, which was introduced and successfully used by Goodman and Pollack in 2005.
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 52C45
zbMATH DE Number: 6010484
zbMATH Keywords: allowable sequences
zbMATH Keywords: combinatorial geometry
reviewed by: Maria A. Hernández Cifre
MaRDI profile type: Publication
full work available at URL: s00454-011-9365-5
OpenAlex ID: W2076653520
cites work: Cutting disjoint disks by straight lines
cites work: Separating convex sets in the plane
cites work: Q5490271
cites work: Covering convex sets with non-overlapping polygons
cites work: The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
cites work: Q5824053
cites work: On the combinatorial classification of nondegenerate configurations in the plane
cites work: The combinatorial encoding of disjoint convex sets in the plane
cites work: Separating plane convex sets.
cites work: Q4657586
cites work: On the number of balanced lines
cites work: A seperation property of plane convex sets.
cites work: 2N noncollinear points determine at least 2N directions
DOI: 10.1007/S00454-011-9365-5
description: scientific article; zbMATH DE number 6010484