Distinct distances between points and lines

DOI10.1016/J.COMGEO.2017.10.008MaRDI QIDQ1702254zbMATH OpenOpenAlexFDO

Authors Micha Sharir, Shakhar Smorodinsky, Claudiu Valculescu, Frank de Zeeuw

Publication date 28 February 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.09006

zbMATH Keywords

discrete geometryincidence geometrydistinct point-line distancesdistinct point-plane distances

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

Abstract: We show that for $m$ points and $n$ lines in the real plane, 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}lenle{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 $O(n^{3/2})$ points where two or more circles are tangent, improving the previously best known bound of $O(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.

Recommendations

• Distinct distances on two lines
• Distinct distances on algebraic curves in the plane
• Distinct distances between points and lines in \(\mathbb{F}_q^2\)
• Distinct Distances on Algebraic Curves in the Plane
• Few distinct distances implies no heavy lines or circles

Cites work

• scientific article; zbMATH DE number 1303711 (Why is no real title available?)
• scientific article; zbMATH DE number 2145241 (Why is no real title available?)
• scientific article; zbMATH DE number 3893918 (Why is no real title available?)
• A combinatorial problem on polynomials and rational functions
• A semi-algebraic version of Zarankiewicz's problem
• An improved bound on the number of point-surface incidences in three dimensions
• Apollonius by Inversion
• Combinatorial complexity bounds for arrangements of curves and spheres
• Common tangents to spheres in \(\mathbb R^{3}\)
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Distinct distances in the plane
• Distinct distances on two lines
• Extremal problems in discrete geometry
• Intersection reverse sequences and geometric applications.
• Lenses in arrangements of pseudo-circles and their applications
• New bounds on curve tangencies and orthogonalities
• On Sets of Distances of n Points
• On the Erdős distinct distances problem in the plane
• On the Number of Incidences Between Points and Curves
• On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
• Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
• Unit distances in three dimensions

Cited in

(13)

• Distinct distances on two lines
• Distances on the tropical line determined by two points
• Distinct distances between points and lines in \(\mathbb{F}_q^2\)
• Incidences in three dimensions and distinct distances in the plane
• Distinct distances on non-ruled surfaces and between circles
• Distinct Distances Between a Circle and a Generic Set
• Distinct distances between a collinear set and an arbitrary set of points
• How to find a point on a line within a fixed distance
• Incidences in three dimensions and distinct distances in the plane
• Few distinct distances implies no heavy lines or circles
• Sets with few distinct distances do not have heavy lines
• Distinct distances from three points
• On distinct distances between a variety and a point set

This page was built for publication: Distinct distances between points and lines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702254)