5 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…