---
_id: '4066'
abstract:
- lang: eng
text: 'We consider several problems involving points and planes in three dimensions.
Our main results are: (i) The maximum number of faces boundingm distinct cells
in an arrangement ofn planes isO(m 2/3 n logn +n 2); we can calculatem such cells
specified by a point in each, in worst-case timeO(m 2/3 n log3 n+n 2 logn). (ii)
The maximum number of incidences betweenn planes andm vertices of their arrangement
isO(m 2/3 n logn+n 2), but this number is onlyO(m 3/5– n 4/5+2 +m+n logm), for
any>0, for any collection of points no three of which are collinear. (iii)
For an arbitrary collection ofm points, we can calculate the number of incidences
between them andn planes by a randomized algorithm whose expected time complexity
isO((m 3/4– n 3/4+3 +m) log2 n+n logn logm) for any>0. (iv) Givenm points andn
planes, we can find the plane lying immediately below each point in randomized
expected timeO([m 3/4– n 3/4+3 +m] log2 n+n logn logm) for any>0. (v) The maximum
number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an
arrangement ofn hyperplanes ind dimensions,d>3, isO(m 2/3 n d/3 logn+n d–1).
This is also an upper bound for the number of incidences betweenn hyperplanes
ind dimensions andm vertices of their arrangement. The combinatorial bounds in
(i) and (v) and the general bound in (ii) are almost tight.'
acknowledgement: "Supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by
NSF Grant CCR-8714565. Work on this paper by the first author has been supported
by Amoco Fnd. Fac. Dev. Comput. Sci. I-6-44862 and by NSF Grant CCR-87t4565. Work
by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129,
by National Science Foundation Grant DCR-82-20085, by grants from the Digital Equipment
Corporation, and the IBM Corporation, and by a research grant from the NCRD--the
Israeli National Council for Research and Development. An abstract of this\r\npaper
has appeared in the Proceedings of the 13th International Mathematical Programming
Symposium, Tokyo, 1988, p. 147"
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: Edelsbrunner H, Guibas L, Sharir M. The complexity of many cells in arrangements
of planes and related problems. *Discrete & Computational Geometry*.
1990;5(1):197-216. doi:10.1007/BF02187785
apa: Edelsbrunner, H., Guibas, L., & Sharir, M. (1990). The complexity of many
cells in arrangements of planes and related problems. *Discrete & Computational
Geometry*. Springer. https://doi.org/10.1007/BF02187785
chicago: Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity
of Many Cells in Arrangements of Planes and Related Problems.” *Discrete &
Computational Geometry*. Springer, 1990. https://doi.org/10.1007/BF02187785.
ieee: H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity of many cells in
arrangements of planes and related problems,” *Discrete & Computational
Geometry*, vol. 5, no. 1. Springer, pp. 197–216, 1990.
ista: Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity of many cells in
arrangements of planes and related problems. Discrete & Computational Geometry.
5(1), 197–216.
mla: Edelsbrunner, Herbert, et al. “The Complexity of Many Cells in Arrangements
of Planes and Related Problems.” *Discrete & Computational Geometry*,
vol. 5, no. 1, Springer, 1990, pp. 197–216, doi:10.1007/BF02187785.
short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & Computational Geometry
5 (1990) 197–216.
date_created: 2018-12-11T12:06:44Z
date_published: 1990-03-01T00:00:00Z
date_updated: 2022-02-22T11:02:41Z
day: '01'
doi: 10.1007/BF02187785
extern: '1'
intvolume: ' 5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187785
month: '03'
oa_version: None
page: 197 - 216
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2054'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The complexity of many cells in arrangements of planes and related problems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...