Sphere-and-point incidence relations in high dimensions with applications to unit distances and furthest-neighbor pairs |
| |
Authors: | F. R. K. Chung |
| |
Affiliation: | (1) Bell Communications Research, 07960 Morristown, NJ, USA |
| |
Abstract: | Forn points in three-dimensional Euclidean space, the number of unit distances is shown to be no more thancn8/5. Also, we prove that the number of furthest-neighbor pairs forn points in 3-space is no more thancn8/5, provided no three points are collinear. Both these results follow from the following incidence relation of spheres and points in 3-space. Namely, the number of incidences betweenn points andt spheres is at mostcn4/5t4/5 if no three points are collinear andn3/2>t>n1/4. The proof is based on a point-and-line incidence relation established by Szemerédi and Trotter. Analogous versions for higher dimensions are also given. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|