A Helly-type theorem for hyperplane transversals to well-separated convex sets

B. Aronov, J. E. Goodman, R. Pollack, R. Wenger

    Research output: Contribution to journalArticle

    Abstract

    Let S be a finite collection of compact convex sets in ℝd. Let D(S) be the largest diameter of any member of S. We say that the collection S is ε-separated if, for every 0 < k < d, any k of the sets can be separated from any other d - k of the sets by a hyperplane more than εD(S)/2 away from all d of the sets. We prove that if S is an ε-separated collection of at least N (ε) compact convex sets in ℝd and every 2d + 2 members of S are met by a hyperplane, then there is a hyperplane meeting all the members of S. The number N (ε) depends both on the dimension d and on the separation parameter ε. This is the first Helly-type theorem known for hyperplane transversals to compact convex sets of arbitrary shape in dimension greater than one.

    Original languageEnglish (US)
    Pages (from-to)507-517
    Number of pages11
    JournalDiscrete and Computational Geometry
    Volume25
    Issue number4
    DOIs
    StatePublished - Jun 2001

    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 'A Helly-type theorem for hyperplane transversals to well-separated convex sets'. Together they form a unique fingerprint.

  • Cite this