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

Boris Aronov, Jacob E. Goodman, Richard Pollack, Rephael Wenger

    Research output: Contribution to conferencePaper

    Abstract

    Let S be a family of compact convex sets in Rd. Let D(S) be the largest diameter of any member of S. The family 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) away from all d of the sets. We prove that if S is an ε-separated family of at least N(ε) compact convex sets in Rd 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)
    Pages57-63
    Number of pages7
    StatePublished - 2000
    Event16th Annual Symposium on Computational Geometry - Hong Kong, Hong Kong
    Duration: Jun 12 2000Jun 14 2000

    Other

    Other16th Annual Symposium on Computational Geometry
    CityHong Kong, Hong Kong
    Period6/12/006/14/00

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Helly-type theorem for hyperplane transversals to well-separated convex sets'. Together they form a unique fingerprint.

  • Cite this

    Aronov, B., Goodman, J. E., Pollack, R., & Wenger, R. (2000). Helly-type theorem for hyperplane transversals to well-separated convex sets. 57-63. Paper presented at 16th Annual Symposium on Computational Geometry, Hong Kong, Hong Kong, .