首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Few distinct distances implies no heavy lines or circles
Authors:Adam Sheffer  Joshua Zahl  Frank de Zeeuw
Institution:1.School of Computer Science,Tel Aviv University,Tel Aviv,Israel;2.Department of Mathematics,MIT,Cambridge,USA;3.EPFL,Lausanne,Switzerland
Abstract:We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set \(\mathcal{P}\) of n points determines o(n) distinct distances, then no line contains Ω(n 7/8) points of \(\mathcal{P}\) and no circle contains Ω(n 5/6) points of \(\mathcal{P}\).We rely on the partial variant of the Elekes-Sharir framework that was introduced by Sharir, Sheffer, and Solymosi in 19] for bipartite distinct distance problems. To prove our bound for the case of lines we combine this framework with a theorem from additive combinatorics, and for our bound for the case of circles we combine it with some basic algebraic geometry and a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang 20].A significant difference between our approach and that of 19] (and of other related results) is that instead of dealing with distances between two point sets that are restricted to one-dimensional curves, we consider distances between one set that is restricted to a curve and one set with no restrictions on it.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号