On the zone of a surface in a hyperplane arrangement

Boris Aronov, Marco Pellegrini, Micha Sharir

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Let H be a collection of n hyperplanes in ℝd, let A denote the arrangement of H, and let σ be a (d-1)-dimensional algebraic surface of low degree, or the boundary of a convex set in ℝd. The zone of σ in A is the collection of cells of A crossed by σ. We show that the total number of faces bounding the cells of the zone of σ is O(nd-1 log n). More generally, if σ has dimension p, 0≤p<d, this quantity is O(n[(d+p)/2]) for d-p even and O(n[(d+p)/2] log n) for d-p odd. These bounds are tight within a logarithmic factor.

    Original languageEnglish (US)
    Pages (from-to)177-186
    Number of pages10
    JournalDiscrete & Computational Geometry
    Volume9
    Issue number1
    DOIs
    StatePublished - Dec 1993

    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 'On the zone of a surface in a hyperplane arrangement'. Together they form a unique fingerprint.

    Cite this