کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868452 | 1439977 | 2018 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Distinct distances between points and lines
ترجمه فارسی عنوان
فاصله های متمایز بین نقاط و خطوط
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
هندسه بروز، هندسه گسسته،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 69, June 2018, Pages 2-15
Journal: Computational Geometry - Volume 69, June 2018, Pages 2-15
نویسندگان
Micha Sharir, Shakhar Smorodinsky, Claudiu Valculescu, Frank de Zeeuw,