Improved bounds for geometric permutations

DOI10.1137/110835918zbMATH Open1255.52008arXiv1007.3244OpenAlexW2570601084MaRDI QIDQ2903522FDOQ2903522

Authors: Natan Rubin, Micha Sharir 

Publication date: 10 August 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: We show that the number of geometric permutations of an arbitrary collection of $n$ pairwise disjoint convex sets in $mathbb{R}^d$, for $dgeq3$, is $O(n^{2d-3}logn)$, improving Wenger's 20 years old bound of $O(n^{2d-2})$.

Full work available at URL: https://arxiv.org/abs/1007.3244

Recommendations

• Sharp bounds on geometric permutations of pairwise disjoint balls in \(\mathbb{R}^d\)
• scientific article; zbMATH DE number 2089216
• A tight bound on the number of geometric permutations of convex fat objects in \(\mathbb{R}^d\)
• Upper bounds on geometric permutations for convex sets
• The maximal number of geometric permutations for \(n\) disjoint translates of a convex set in \(\mathbb R\) is \(\Omega(n)\)

zbMATH Keywords

general positioncombinatorial complexitygeometric permutationsarrangements of great circles on a sphere

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Combinatorial complexity of geometric structures (52C45) Convex sets in (3) dimensions (including convex surfaces) (52A15)

Cited In (15)

• Title not available (Why is that?)
• Geometric permutations of non-overlapping unit balls revisited
• Block size in geometric(\(p\))-biased permutations
• Geometric permutations of balls with bounded size disparity.
• A constant bound for geometric permutations of disjoint unit balls
• Geometric permutations
• A tight bound on the number of geometric permutations of convex fat objects in \(\mathbb{R}^d\)
• The maximal number of geometric permutations for \(n\) disjoint translates of a convex set in \(\mathbb R\) is \(\Omega(n)\)
• Sharp bounds on geometric permutations of pairwise disjoint balls in \(\mathbb{R}^d\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometric permutations of high dimensional spheres.
• On neighbors in geometric permutations.
• Extending permutation arrays: improving MOLS bounds
• A tight bound on the number of geometric permutations of convex fat objects in \(\mathbb{R}^d\)

This page was built for publication: Improved bounds for geometric permutations

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