Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Distinct distances between points and lines
 
research article

Distinct distances between points and lines

Sharir, Micha
•
Smorodinsky, Shakhar
•
Valculescu, Claudiu
Show more
2018
Computational Geometry-Theory And Applications

We show that for m points and n lines in R-2, the number of distinct distances between the points and the lines is Omega(m(1/5)n(3/5)), as long as m(1/2) <= n <= m(2). 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 Omega(m(4/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 Omicron(n(3/2)) points where two or more circles are tangent, improving the previously best known bound of Omicron(n(3/2) logn). 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. (C) 2017 Elsevier B.V. All rights reserved.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.comgeo.2017.10.008
Web of Science ID

WOS:000417965300002

Author(s)
Sharir, Micha
Smorodinsky, Shakhar
Valculescu, Claudiu
De Zeeuw, Frank
Date Issued

2018

Publisher

Elsevier Science Bv

Published in
Computational Geometry-Theory And Applications
Volume

69

Start page

2

End page

15

Subjects

Incidence geometry

•

Discrete geometry

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
January 15, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/143957
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés