9 papers
Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case where truly subquadratic-time algorithms…
Triangulating a Polygon with Holes in Optimal (Deterministic) Time
Timothy M. Chan
We consider the problem of triangulating a polygon with vertices and holes, or relatedly the problem of computing the trapezoidal decomposition of a collection of disjo…
Computing the Girth of a Segment Intersection Graph
Timothy M. Chan, Yuancheng Yu
We present an algorithm that computes the girth of the intersection graph of given line segments in the plane in expected time. This is the first such algorithm…
Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
We give the first truly subquadratic time algorithm, with running time, for computing the diameter of an -vertex unit-disk graph, resolving a central open prob…
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,…
An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism
Timothy M. Chan, Pingan Cheng, Da Wei Zheng
We present the first optimal randomized algorithm for constructing the order- Voronoi diagram of points in two dimensions. The expected running time is , wh…