Geometric permutations induced by line transversals through a fixed point

Boris Aronov, Shakhar Smorodinsky

    Research output: Contribution to journalArticlepeer-review

    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 ?1, d ?1) and K(n, d ?1), where K(n, d) Σi=0d (in?1) = Θ(nd) 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 line transversals 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 languageEnglish (US)
    Pages (from-to)285-294
    Number of pages10
    JournalDiscrete and Computational Geometry
    Volume34
    Issue number2
    DOIs
    StatePublished - Aug 2005

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics

    Fingerprint Dive into the research topics of 'Geometric permutations induced by line transversals through a fixed point'. Together they form a unique fingerprint.

    Cite this