2 papers
cs.CG2024
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…
cs.CG2023
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…