On the zone of a surface in a hyperplane arrangement

Boris Aronov; Marco Pellegrini; Micha Sharir

doi:10.1007/BF02189317

On the zone of a surface in a hyperplane arrangement

Boris Aronov, Marco Pellegrini, Micha Sharir

Research output: Contribution to journal › Article › peer-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(n^d-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 language	English (US)
Pages (from-to)	177-186
Number of pages	10
Journal	Discrete & Computational Geometry
Volume	9
Issue number	1
DOIs	https://doi.org/10.1007/BF02189317
State	Published - Dec 1993

ASJC Scopus subject areas

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

Access to Document

10.1007/BF02189317

Cite this

@article{8a1135b866564e2eb985e0accaf3b9ed,

title = "On the zone of a surface in a hyperplane arrangement",

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+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.",

author = "Boris Aronov and Marco Pellegrini and Micha Sharir",

year = "1993",

month = dec,

doi = "10.1007/BF02189317",

language = "English (US)",

volume = "9",

pages = "177--186",

journal = "Discrete & Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - On the zone of a surface in a hyperplane arrangement

AU - Aronov, Boris

AU - Pellegrini, Marco

AU - Sharir, Micha

PY - 1993/12

Y1 - 1993/12

N2 - 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+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.

AB - 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+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.

UR - http://www.scopus.com/inward/record.url?scp=21144464172&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21144464172&partnerID=8YFLogxK

U2 - 10.1007/BF02189317

DO - 10.1007/BF02189317

M3 - Article

AN - SCOPUS:21144464172

SN - 0179-5376

VL - 9

SP - 177

EP - 186

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

IS - 1

ER -

On the zone of a surface in a hyperplane arrangement

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this