## Abstract

A line transversal of a family S of n pairwise disjoint convex objects is a straight line meeting all members of S. A geometric permutation of S is the pair of orders in which members of S are met by a line transversal, one order being the reverse of the other. In this note we consider a long-standing open problem in transversal theory, namely that of determining the largest number of geometric permutations that a family of n pairwise disjoint convex objects in ℝ^{d} can admit. We settle a restricted variant of this problem. Specifically, we show that the maximum number of those geometric permutations to a family of n > 2 pairwise disjoint convex objects that are induced by lines passing through any fixed point is between K(n - l, d - 1) and K(n, d - 1), where K(n, d) = Σ_{i}^{d}=0 (^{n-1} _{i}) = ⊙(n^{d}) is the number of pairs of antipodal cells in a simple arrangement of n great (d - 1)-spheres in a d-sphere. By a similar argument, we show that the maximum number of connected components of the space of all lines transversal through a fixed point to a family of n > 2 possibly intersecting convex objects is K(n, d -1). Finally, we refute a conjecture of Sharir and Smorodinsky on the number of neighbor pairs in geometric permutations and offer an alternative conjecture which may be a first step towards solving the aforementioned general problem of bounding the number of geometric permutations.

Original language | English (US) |
---|---|

Pages | 251-256 |

Number of pages | 6 |

State | Published - 2005 |

Event | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005 |

### Other

Other | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | Vancouver, BC |

Period | 1/23/05 → 1/25/05 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)