6 citations · 9 across the 4 of their papers we have counts for
8 papers
Dynamic Geometric Set Cover, Revisited
Timothy M. Chan, Qizheng He, Subhash Suri +1
Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may b…
More on Change-Making and Related Problems
Timothy M. Chan, Qizheng He
Given a set of integer-valued coin types and a target value , the well-known change-making problem asks for the minimum number of coins that sum to , assuming an unlimite…
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time
Timothy M. Chan, Qizheng He
We study geometric set cover problems in dynamic settings, allowing insertions and deletions of points and objects. We present the first dynamic data structure that can maintain an…
Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing
Younan Gao, Meng He, Yakov Nekrich
Under the word RAM model, we design three data structures that can be constructed in time over points in an grid. The first data structure is an…
Faster Approximation Algorithms for Geometric Set Cover
Timothy M. Chan, Qizheng He
We improve the running times of -approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering po…
Further Results on Colored Range Searching
Timothy M. Chan, Qizheng He, Yakov Nekrich
We present a number of new results about range searching for colored (or "categorical") data: 1. For a set of colored points in three dimensions, we describe randomized data st…