On the zone of a surface in a hyperplane arrangement

Boris Aronov, Micha Sharir

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 body 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).

    Original languageEnglish (US)
    Title of host publicationAlgorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings
    EditorsFrank Dehne, Jorg-Rudiger Sack, Nicola Santoro
    PublisherSpringer Verlag
    Pages13-19
    Number of pages7
    ISBN (Print)9783540475668
    DOIs
    StatePublished - 1991
    Event2nd Workshop on Algorithms and Data Structures, WADS 1991 - Ottawa, Canada
    Duration: Aug 14 1991Aug 16 1991

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume519 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other2nd Workshop on Algorithms and Data Structures, WADS 1991
    Country/TerritoryCanada
    CityOttawa
    Period8/14/918/16/91

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    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