Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6868452 | Computational Geometry | 2018 | 14 Pages |
Abstract
We show that for m points and n lines in R2, the number of distinct distances between the points and the lines is Ω(m1/5n3/5), as long as m1/2â¤nâ¤m2. We also prove that for any m points in the plane, not all on a line, the number of distances between these points and the lines that they span is Ω(m4/3). The problem of bounding the number of distinct point-line distances can be reduced to the problem of bounding the number of tangent pairs among a finite set of lines and a finite set of circles in the plane, and we believe that this latter question is of independent interest. In the same vein, we show that n circles in the plane determine at most O(n3/2) points where two or more circles are tangent, improving the previously best known bound of O(n3/2logâ¡n). Finally, we study three-dimensional versions of the distinct point-line distances problem, namely, distinct point-line distances and distinct point-plane distances. The problems studied in this paper are all new, and the bounds that we derive for them, albeit most likely not tight, are non-trivial to prove. We hope that our work will motivate further studies of these and related problems.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Micha Sharir, Shakhar Smorodinsky, Claudiu Valculescu, Frank de Zeeuw,