4 papers · 1 filter
On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects
Timothy M. Chan, Chaya Keller, Shakhar Smorodinsky
The hypergraph Zarankiewicz's problem, introduced by Erdős in 1964, asks for the maximum number of hyperedges in an -partite hypergraph with vertices in each part that does…
Dynamic Geometric Connectivity in the Plane with Constant Query Time
Timothy M. Chan, Zhengcheng Huang
We present the first fully dynamic connectivity data structures for geometric intersection graphs achieving constant query time and sublinear amortized update time for most types o…
Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane
Timothy M. Chan, Pingan Cheng, Da Wei Zheng
Polynomial partitioning techniques have recently led to improved geometric data structures for a variety of fundamental problems related to semialgebraic range searching and inters…
Fully Dynamic Geometric Vertex Cover and Matching
Sujoy Bhore, Timothy M. Chan
In this work, we study two fundamental graph optimization problems, minimum vertex cover (MVC) and maximum-cardinality matching (MCM), for intersection graphs of geometric objects,…