10.1007/3-540-52921-7_91
Herbert Edelsbrunner
Herbert
Edelsbrunner0000-0002-9823-6833
Sharir, Micha
Micha
Sharir
A hyperplane Incidence problem with applications to counting distances
LNCS
Springer
1990
2018-12-11T12:06:45Z
2019-04-26T07:22:39Z
conference
https://research-explorer.app.ist.ac.at/record/4067
https://research-explorer.app.ist.ac.at/record/4067.json
This paper proves an O(m 2/3 n 2/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.