Abstract
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.
Research of the first author was supported by the National Science Foundation under grant CCR-8714565. Work of the second author was supported by Office of Naval Research Grants DCR-83-20085 and CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD — the Israeli National Council for Research and Development, and the Fund for Basic Research in Electronics, Computers and Communication administered by the Israeli Academy of Sciences.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. Agarwal, H. Edelsbrunner, O. Schwarzkopf and E. Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. To appear in “Proc. 6th Ann. Sympos. Comput. Geom. 1990”.
B. Bollobás. Extremal Graph Theory. London Math. Soc. Monographs, No. 11, Academic Press, London, 1978.
A. Brønsted. An Introduction to Convex Polytopes. Grad. Texts in Math., Springer-Verlag, New York, 1983.
K. L. Clarkson, H. Edelsbrunner, L. J. Guibas, M. Sharir and E. Welzl. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Comput. Geom. 5 (1990).
K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4 (1989), 387–421.
B. Delaunay. Sur la sphère vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk 7 (1934), 793–800.
H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, Germany, 1987.
P. Erdös. On sets of distances of n points. Amer. Math. Monthly 53 (1946), 248–250.
P. Erdös. On sets of distances of n points in Euclidean space. Magyar Tud. Akad. Mat. Kutaló Int. Kozl. 5 (1960), 165–169.
B. Grünbaum. A proof of Vázsonyi's conjecture. Bull. Res. Council Israel Sect. A 6 (1956), 77–78.
A. Heppes. Beweis einer Vermutung von A. Vázsonyi. Acta Math. Acad. Sci. Hungar. 7 (1956), 463–466.
W. O. J. Moser and J. Pach. Research problems in discrete geometry. Manuscript, Dept. Math., McGill Univ., Montreal, Quebec, 1986.
J. Spencer, E. Szemerédi and W. T. Trotter, Jr. Unit distances in the Euclidean plane. In Graph Theory and Combinatorics, Academic Press, London, 1984, 293–303.
S. Straszewicz. Sur un problème geometrique de P. Erdös. Bull. Acad. Polon. Sci. Cl. III 5 (1957), 39–40.
E. Szemerédi and W. T. Trotter, Jr. Extremal problems in discrete geometry. Combinatorica 3 (1983), 381–392.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Edelsbrunner, H., Sharir, M. (1990). A hyperplane Incidence problem with applications to counting distances. In: Asano, T., Ibaraki, T., Imai, H., Nishizeki, T. (eds) Algorithms. SIGAL 1990. Lecture Notes in Computer Science, vol 450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52921-7_91
Download citation
DOI: https://doi.org/10.1007/3-540-52921-7_91
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-52921-7
Online ISBN: 978-3-540-47177-6
eBook Packages: Springer Book Archive