Improved bounds for geometric permutations

DOI10.1137/110835918MaRDI QIDQ2903522zbMATH OpenOpenAlexFDO

Authors Natan Rubin, Micha Sharir

Publication date 10 August 2012

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

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

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)

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})$.

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)\)

Cited in

(16)

• A tight bound on the number of geometric permutations of convex fat objects in \(\mathbb{R}^d\)
• scientific article; zbMATH DE number 7559240 (Why is no real title available?)
• 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\)
• Bounding the number of geometric permutations induced by \(k\)-transversals
• scientific article; zbMATH DE number 7324093 (Why is no real title available?)
• scientific article; zbMATH DE number 2089216 (Why is no real title available?)
• Geometric permutations of high dimensional spheres.
• On neighbors in geometric permutations.
• Extending permutation arrays: improving MOLS bounds

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)