On neighbors in geometric permutations.
type: Item
instance of: scholarly article
title: On neighbors in geometric permutations.
zbMATH Open document ID: 1042.52004
DOI: 10.1016/S0012-365X(03)00052-9
author: Shakhar Smorodinsky
author: Micha Sharir
published in: Discrete Mathematics
publication date: 2003-07-29T00:00:00Z
review text: Let \(S\) be a family of disjoint convex bodies in \({\mathbb R}^d\). A line that intersects every member of \(S\) is called a line transversal of \(S\). Each line transversal \(\ell \) of \(S\) induces a pair of linear orderings of \(S\) by the order in which the members of \(S\) are met by \(\ell \) (one order being the reverse of the other). These pairs of orders are called geometric permutations of \(S\), and the subject of this paper is to find upper bounds for the number \(GP(S)\) of these permutations. To do this, the following notion is introduced. Two bodies \(a,b\in S\) are called neighbors if there exists a line transversal \(\ell \) of \(S\) such that \(a\) and \(b\) are consecutive elements of the geometric permutation induced by \(\ell \). The set of neighbor pairs in \(S\) is then denoted by \(N(S)\), and it turns out that \(GP(S)=O(\left| N(S)\right| ^{d-1})\). The main result says that \( \left| N(S)\right| =O(n)\) in the plane, which leads to a new proof of the known fact \(GP(S)=O(n)\) for \(d=2\). It is conjectured that \(\left| N(S)\right| =O(n)\) for all dimensions \(d\), which would imply the tight bound \(GP(S)=O(n^{d-1})\).
Mathematics Subject Classification ID: 52A35
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 52A20
Mathematics Subject Classification ID: 52A37
Mathematics Subject Classification ID: 52C45
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 1956053
zbMATH Keywords: geometric permutations
zbMATH Keywords: line transversals
reviewed by: Johann Linhart
MaRDI profile type: Publication
cites work: Quasi-planar graphs have a linear number of edges
cites work: Q4763390
cites work: The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
cites work: Hadwiger's Transversal Theorem In Higher Dimensions
cites work: Q3138749
cites work: Geometric permutations and common transversals
cites work: The different ways of stabbing disjoint convex sets
cites work: A constant bound for geometric permutations of disjoint unit balls
cites work: A tight bound on the number of geometric permutations of convex fat objects in {\huge $\mathbf{\reals^d}$}
cites work: The Partition Technique for Overlays of Envelopes
cites work: Sharp bounds on geometric permutations of pairwise disjoint balls in \(\mathbb{R}^d\)
cites work: Upper bounds on geometric permutations for convex sets
cites work: Shape sensitive geometric permutations
full work available at URL: s0012-365x(03)00052-9
OpenAlex ID: W1991624414
description: scientific article; zbMATH DE number 1956053