Geometric permutations of disjoint unit spheres
A line transversal for a sequence \({\mathcal K}=K_1,\ldots, K_n\) of pair-wise disjoint convex bodies in \(R^d\) is a line \(p\) such that \(p\cap K_i\neq\emptyset\) for each \(i=1,\ldots,n\). Each line transversal \(p\) determines two (opposite) linear orders on \({\mathcal K}\) or equivalently two permutations of \([n]=\{1,\ldots,n\}\) referred to as a (single) geometric permutation of \({\mathcal K}\). The authors study the problem of estimating the number of geometric permutations for the case of families of pair-wise disjoint unit balls in \(R^d\). They show that in general there exist at most \(3\) geometric permutations and not more than \(2\) if \(n\geq 9\). The proof is based on the fact that some geometric permutations are incompatible in the sense that they cannot both appear in the same family \({\mathcal K}\). The key observation is that the permutations \((ABCD, BADC)\) are incompatible for unit balls, although they may appear together in a family of pair-wise disjoint balls of different radii.
- A constant bound for geometric permutations of disjoint unit balls
- A Helly-type theorem for line transversals to disjoint unit balls
- A tight bound on the number of geometric permutations of convex fat objects in \(\mathbb{R}^d\)
- Algorithms - ESA 2003
- Forbidden families of geometric permutations in \(\mathbb R^{d}\)
- Geometric permutations of disjoint translates of convex sets
- Geometric permutations of high dimensional spheres.
- scientific article; zbMATH DE number 431990 (Why is no real title available?)
- scientific article; zbMATH DE number 1182897 (Why is no real title available?)
- scientific article; zbMATH DE number 2209714 (Why is no real title available?)
- Sharp bounds on geometric permutations of pairwise disjoint balls in \(\mathbb{R}^d\)
- The different ways of stabbing disjoint convex sets
- The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
- The triples of geometric permutations for families of disjoint translates
- Upper bounds on geometric permutations for convex sets
- The \(T(4)\) property of families of unit disks
- Geometric permutations of disjoint translates of convex sets
- A constant bound for geometric permutations of disjoint unit balls
- Geometric permutations of higher dimensional spheres
- Sharp bounds on geometric permutations of pairwise disjoint balls in \(\mathbb{R}^d\)
- On the number of directions determined by the common tangents to a family of pairwise disjoint convex sets in the plane
- Helly numbers of acyclic families
- Line transversals to disjoint balls
- Helly-type theorems for line transversals to disjoint unit balls
- Geometric permutations of non-overlapping unit balls revisited
- Inflating balls is NP-hard
- scientific article; zbMATH DE number 7559240 (Why is no real title available?)
- Some discrete properties of the space of line transversals to disjoint balls
This page was built for publication: Geometric permutations of disjoint unit spheres
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1776899)
