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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery
Pages1398-1413
Number of pages16
ISBN (Electronic)9781611977554
StatePublished - 2023
Externally publishedYes
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: Jan 22 2023Jan 25 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2023-January

Conference

Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Country/TerritoryItaly
CityFlorence
Period1/22/231/25/23

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings'. Together they form a unique fingerprint.

Cite this