Showing 2026Show all
3 papers · 1 filter
cs.CG2026
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…
cs.CG2026
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…
cs.CG2026
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…