On the zone of a surface in a hyperplane arrangement

Boris Aronov; Micha Sharir

doi:10.1007/BFb0028245

On the zone of a surface in a hyperplane arrangement

Boris Aronov, Micha Sharir

Research output: Chapter in Book/Report/Conference proceeding › Conference 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(n^d−1 log n).

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings
Editors	Frank Dehne, Jorg-Rudiger Sack, Nicola Santoro
Publisher	Springer Verlag
Pages	13-19
Number of pages	7
ISBN (Print)	9783540475668
DOIs	https://doi.org/10.1007/BFb0028245
State	Published - 1991
Event	2nd Workshop on Algorithms and Data Structures, WADS 1991 - Ottawa, Canada Duration: Aug 14 1991 → Aug 16 1991

Publication series

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

Other

Other	2nd Workshop on Algorithms and Data Structures, WADS 1991
Country/Territory	Canada
City	Ottawa
Period	8/14/91 → 8/16/91

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/BFb0028245

Cite this

Aronov, B., & Sharir, M. (1991). On the zone of a surface in a hyperplane arrangement. In F. Dehne, J-R. Sack, & N. Santoro (Eds.), Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings (pp. 13-19). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 519 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0028245

On the zone of a surface in a hyperplane arrangement. / Aronov, Boris; Sharir, Micha.
Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Nicola Santoro. Springer Verlag, 1991. p. 13-19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 519 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aronov, B & Sharir, M 1991, On the zone of a surface in a hyperplane arrangement. in F Dehne, J-R Sack & N Santoro (eds), Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 519 LNCS, Springer Verlag, pp. 13-19, 2nd Workshop on Algorithms and Data Structures, WADS 1991, Ottawa, Canada, 8/14/91. https://doi.org/10.1007/BFb0028245

Aronov B, Sharir M. On the zone of a surface in a hyperplane arrangement. In Dehne F, Sack J-R, Santoro N, editors, Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. Springer Verlag. 1991. p. 13-19. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0028245

Aronov, Boris ; Sharir, Micha. / On the zone of a surface in a hyperplane arrangement. Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Nicola Santoro. Springer Verlag, 1991. pp. 13-19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{100378ab9b154b20bd561a5bab8482b5,

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

author = "Boris Aronov and Micha Sharir",

note = "Funding Information: *Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-gINJ-1284, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F. --the German Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences. ?Department of Computer Science, Polytechnic University, Brooklyn, NY 11201 USA ICourant Institute of Mathematical Sciences, New York University, and School of Mathematical Sciences, Tel Avlv University, Tel Aviv, Israel Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; 2nd Workshop on Algorithms and Data Structures, WADS 1991 ; Conference date: 14-08-1991 Through 16-08-1991",

year = "1991",

doi = "10.1007/BFb0028245",

language = "English (US)",

isbn = "9783540475668",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "13--19",

editor = "Frank Dehne and Jorg-Rudiger Sack and Nicola Santoro",

booktitle = "Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings",

}

TY - GEN

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

AU - Aronov, Boris

AU - Sharir, Micha

N1 - Funding Information: *Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-gINJ-1284, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F. --the German Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences. ?Department of Computer Science, Polytechnic University, Brooklyn, NY 11201 USA ICourant Institute of Mathematical Sciences, New York University, and School of Mathematical Sciences, Tel Avlv University, Tel Aviv, Israel Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1991.

PY - 1991

Y1 - 1991

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

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

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

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

U2 - 10.1007/BFb0028245

DO - 10.1007/BFb0028245

M3 - Conference contribution

AN - SCOPUS:85032030003

SN - 9783540475668

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 19

BT - Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Santoro, Nicola

PB - Springer Verlag

T2 - 2nd Workshop on Algorithms and Data Structures, WADS 1991

Y2 - 14 August 1991 through 16 August 1991

ER -

On the zone of a surface in a hyperplane arrangement

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this