# A hyperplane incidence problem with applications to counting distances

Edelsbrunner H, Sharir M. 1991.A hyperplane incidence problem with applications to counting distances. In: Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, 253–263.

Download

**No fulltext has been uploaded. References only!**

*Book Chapter*|

*Published*|

*English*

**Scopus indexed**

Author

Edelsbrunner, Herbert

^{ISTA}^{}; Sharir, MichaSeries Title

DIMACS Series in Discrete Mathematics and Theoretical Computer Science

Abstract

This paper proves an O(m2/3n2/3 + m + n) upper bound on the number of incidences between m points and n hyperplanes in four dimensions, assuming all points lie on one side of each hyperplane and the points and hyperplanes satisfy certain natural general position conditions. This result has application to various three-dimensional combinatorial distance problems. For example, it implies the same upper bound for the number of bichromatic minimum distance pairs in a set of m blue and n red points in three-dimensional space. This improves the best previous bound for this problem. © Springer-Verlag Berlin Heidelberg 1990.

Publishing Year

Date Published

1991-04-01

Book Title

Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift

Volume

4

Page

253 - 263

ISBN

IST-REx-ID

### Cite this

Edelsbrunner H, Sharir M. A hyperplane incidence problem with applications to counting distances. In:

*Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift*. Vol 4. American Mathematical Society; 1991:253-263.Edelsbrunner, H., & Sharir, M. (1991). A hyperplane incidence problem with applications to counting distances. In

*Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift*(Vol. 4, pp. 253–263). American Mathematical Society.Edelsbrunner, Herbert, and Micha Sharir. “A Hyperplane Incidence Problem with Applications to Counting Distances.” In

*Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift*, 4:253–63. American Mathematical Society, 1991.H. Edelsbrunner and M. Sharir, “A hyperplane incidence problem with applications to counting distances,” in

*Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift*, vol. 4, American Mathematical Society, 1991, pp. 253–263.Edelsbrunner, Herbert, and Micha Sharir. “A Hyperplane Incidence Problem with Applications to Counting Distances.”

*Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift*, vol. 4, American Mathematical Society, 1991, pp. 253–63.**Link(s) to Main File(s)**

Access Level

Closed Access