Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647166 | Discrete Mathematics | 2015 | 9 Pages |
Abstract
Let P be a set of n points in the plane that determines at most n/5 distinct distances. We show that no line can contain more than O(n43/52polylog(n)) points of P. We also show a similar result for rectangular distances, equivalent to distances in the Minkowski plane, where the distance between a pair of points is the area of the axis-parallel rectangle that they span.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Orit E. Raz, Oliver Roche-Newton, Micha Sharir,