
More on ChangeMaking and Related Problems
Given a set of n integervalued coin types and a target value t, the wel...
read it

Faster Algorithms for Largest Empty Rectangles and Boxes
We revisit a classical problem in computational geometry: finding the la...
read it

More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time
We study geometric set cover problems in dynamic settings, allowing inse...
read it

Algorithms, Reductions and Equivalences for Small Weight Variants of AllPairs Shortest Paths
APSP with small integer weights in undirected graphs [Seidel'95, Galil a...
read it

Faster Approximation Algorithms for Geometric Set Cover
We improve the running times of O(1)approximation algorithms for the se...
read it

Further Results on Colored Range Searching
We present a number of new results about range searching for colored (or...
read it

Approximating TexttoPattern Hamming Distances
We revisit a fundamental problem in string matching: given a pattern of ...
read it

Improved Upper and Lower Bounds for LR Drawings of Binary Trees
In SODA'99, Chan introduced a simple type of planar straightline upward...
read it

Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles
In this paper we study two geometric data structure problems in the spec...
read it

Range closestpair search in higher dimensions
Range closestpair (RCP) search is a rangesearch variant of the classic...
read it

Dynamic Geometric Data Structures via Shallow Cuttings
We present new results on a number of fundamental problems about dynamic...
read it

Smallest kEnclosing Rectangle Revisited
Given a set of n points in the plane, and a parameter k, we consider the...
read it

On LocalitySensitive Orderings and their Applications
For any constant d and parameter ε > 0, we show the existence of (roughl...
read it

Stabbing Rectangles by Line Segments  How Decomposition Reduces the ShallowCell Complexity
We initiate the study of the following natural geometric optimization pr...
read it

Orthogonal Point Location and Rectangle Stabbing Queries in 3d
In this work, we present a collection of new results on two fundamental ...
read it

Tree Drawings Revisited
We make progress on a number of open problems concerning the area requir...
read it

Subquadratic Encodings for Point Configurations
For most algorithms dealing with sets of points in the plane, the only r...
read it

Improved Bounds for Drawing Trees on Fixed Points with Lshaped Edges
Let T be an nnode tree of maximum degree 4, and let P be a set of n poi...
read it
Timothy M. Chan
is this you? claim profile