A Bichromatic Incidence Bound and an Application |
| |
Authors: | Ben D Lund George B Purdy Justin W Smith |
| |
Institution: | 1.Department Of Computer Science,University of Cincinnati,Cincinnati,USA |
| |
Abstract: | We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, of which k are colored red, there are O
d
(m
2/3
k
2/3
n
(d−2)/3+kn
d−2+m) incidences between the k red points and m hyperplanes spanned by all n points provided that m=Ω(n
d−2). For the monochromatic case k=n, this was proved by Agarwal and Aronov (Discrete Comput. Geom. 7(4):359–369, 1992). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|