6 citations · 6 across the 11 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures
Timothy M. Chan, Da Wei Zheng
We revisit the classic problem of simplex range searching and related problems in computational geometry. We present a collection of new results which improve previous bounds by mu…
Halving by a Thousand Cuts or Punctures
Sariel Har-Peled, Da Wei Zheng
For point sets $P_1, \ldots, P_\…
Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees
Timothy M. Chan, Da Wei Zheng
We revisit Hopcroft's problem and related fundamental problems about geometric range searching. Given points and lines in the plane, we show how to count the number of poin…