Improved bounds for geometric permutations
type: Item
instance of: scholarly article
zbMATH Open document ID: 1255.52008
DOI: 10.1137/110835918
author: Natan Rubin
author: Micha Sharir
published in: SIAM Journal on Computing
publication date: 2012-08-10T00:00:00Z
full work available at URL: https://arxiv.org/abs/1007.3244
Mathematics Subject Classification ID: 52A20
Mathematics Subject Classification ID: 52C45
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 52A15
zbMATH DE Number: 6064775
zbMATH Keywords: geometric permutations
zbMATH Keywords: arrangements of great circles on a sphere
zbMATH Keywords: combinatorial complexity
zbMATH Keywords: general position
MaRDI profile type: Publication
OpenAlex ID: W2570601084
arXiv ID: 1007.3244
title: Improved bounds for geometric permutations
review text: Let \({\mathcal K }\) be a collection of \(n\) pairwise disjoint convex bodies in \( {\mathbb R}^d \). The authors recall the definition of geometric permutation: If an oriented line meets all these bodies, then it determines a well-defined order, called geometric permutation.NEWLINENEWLINELet \( g_d (n) \) be the maximal possible number of these permutations generated by a set \({\mathcal K }\).NEWLINENEWLINEThe goal of the paper is to improve estimates of \( g_d (n) \) for \( d \geq 3\), obtained in some 20-years-old papers. So, the main results of the paper are:NEWLINENEWLINETheorem 2.5. Any collection of \( n \) pairwise disjoint convex sets in \( {\mathbb R}^3 \) admits at most \( O (n^3 \log n)\) geometric permutations.NEWLINENEWLINETheorem 3.5. Any collection of \( n \) pairwise disjoint convex sets in \( {\mathbb R}^d \), for \( d \geq 3 \), admits at most \( O (n^{2d-3} \log n)\) geometric permutations.NEWLINENEWLINEThe authors formulate also the hypothesis that the correct upper bound of \( g_d (n) \) is close to \( O(n^{d-1})\) for any \( d \geq 3 \), and that \( g_3 (n) = O(n^{3})\).
reviewed by: Vladimir Golubyatnikov
description: scientific article; zbMATH DE number 6064775