TY - GEN

T1 - On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings

AU - Chan, Timothy M.

AU - Har-Peled, Sariel

N1 - Publisher Copyright:
Copyright © 2023 by SIAM.

PY - 2023

Y1 - 2023

N2 - Given a set of points P and a set of regions O, an incidence is a pair (p, o) ∈ P × O such that p ∈ o. We obtain a number of new results on a classical question in combinatorial geometry: What is the number of incidences (under certain restrictive conditions)? We prove a bound of O(kn(log n/log log n)d-1) on the number of incidences between n points and n axis-parallel boxes in ℝd, if no k boxes contain k common points, that is, if the incidence graph between the points and the boxes does not contain Kk, k as a subgraph. This new bound improves over previous work, by Basit, Chernikov, Starchenko, Tao, and Tran (2021), by more than a factor of logd n for d > 2. Furthermore, it matches a lower bound implied by the work of Chazelle (1990), for k = 2, thus settling the question for points and boxes. We also study several other variants of the problem. For halfspaces, using shallow cuttings, we get a linear bound in two and three dimensions. We also present linear (or near linear) bounds for shapes with low union complexity, such as pseudodisks and fat triangles.

AB - Given a set of points P and a set of regions O, an incidence is a pair (p, o) ∈ P × O such that p ∈ o. We obtain a number of new results on a classical question in combinatorial geometry: What is the number of incidences (under certain restrictive conditions)? We prove a bound of O(kn(log n/log log n)d-1) on the number of incidences between n points and n axis-parallel boxes in ℝd, if no k boxes contain k common points, that is, if the incidence graph between the points and the boxes does not contain Kk, k as a subgraph. This new bound improves over previous work, by Basit, Chernikov, Starchenko, Tao, and Tran (2021), by more than a factor of logd n for d > 2. Furthermore, it matches a lower bound implied by the work of Chazelle (1990), for k = 2, thus settling the question for points and boxes. We also study several other variants of the problem. For halfspaces, using shallow cuttings, we get a linear bound in two and three dimensions. We also present linear (or near linear) bounds for shapes with low union complexity, such as pseudodisks and fat triangles.

UR - http://www.scopus.com/inward/record.url?scp=85165870823&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85165870823&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85165870823

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1398

EP - 1413

BT - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

PB - Association for Computing Machinery

T2 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

Y2 - 22 January 2023 through 25 January 2023

ER -