6 citations · 6 across the 11 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
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…
cs.DS2023
Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs
Yi-Jun Chang, Da Wei Zheng
We consider the massively parallel computation (MPC) model, which is a theoretical abstraction of large-scale parallel processing models such as MapReduce. In this model, assuming…
cs.DS2023
Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
Da Wei Zheng, Monika Henzinger
We present an auction algorithm using multiplicative instead of constant weight updates to compute a $(1-\eps)$-approximate maximum weight matching…