Timothy M. Chan

Q: What Schools Are Affiliated With Timothy M. Chan

Timothy M. Chan is affiliated with the following schools: Rice University, University of Waterloo, University of British Columbia, University of Illinois Urbana-Champaign

Timothy M. Chan's AcademicInfluence.com Rankings

Timothy M. Chan

Computer Science

#1970

World Rank

#2046

Historical Rank

Database

#3664

World Rank

#3815

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Why Is Timothy M. Chan Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Timothy Moon-Yew Chan is a Founder Professor in the Department of Computer Science at the University of Illinois at Urbana–Champaign. He was formerly Professor and University Research Chair in the David R. Cheriton School of Computer Science, University of Waterloo, Canada.

(See a Problem?)

Timothy M. Chan's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Optimal output-sensitive convex hull algorithms in two and three dimensions (1996) (353)
More algorithms for all-pairs shortest paths in weighted graphs (2007) (251)
Approximation Algorithms for Maximum Independent Set of Pseudo-Disks (2009) (200)
Orthogonal range searching on the RAM, revisited (2011) (199)
Polynomial-time approximation schemes for packing and piercing fat objects (2003) (184)
Output-sensitive results on convex hulls, extreme points, and related problems (1995) (156)
An optimal randomized algorithm for maximum Tukey depth (2004) (137)
Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus (2000) (137)
Approximate Nearest Neighbor Queries Revisited (1997) (118)
Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling (2012) (118)
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky (2016) (115)
Clustered Integer 3SUM via Additive Combinatorics (2015) (114)
Faster core-set constructions and data stream algorithms in fixed dimensions (2004) (108)
Dynamic planar convex hull operations in near-logarithmic amortized time (1999) (105)
Geometric Applications of a Randomized Optimization Technique (1998) (104)
Optimal Partition Trees (2010) (101)
More planar two-center algorithms (1999) (98)
Random Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions (2000) (94)
Counting inversions, offline orthogonal range counting, and related problems (2010) (91)
Optimal halfspace range reporting in three dimensions (2009) (89)
All-Pairs Shortest Paths with Real Weights in O(n3/log n) Time (2008) (82)
Low-dimensional linear programming with violations (2002) (80)
Klee's Measure Problem Made Easy (2013) (79)
Polynomial Representations of Threshold Functions and Algorithmic Applications (2016) (78)
All-pairs shortest paths for unweighted undirected graphs in o(mn) time (2012) (75)
On Hardness of Jumbled Indexing (2014) (73)
Necklaces, Convolutions, and X+Y (2006) (73)
A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries (2006) (72)
Exact algorithms and APX-hardness results for geometric packing and covering problems (2014) (72)
A (slightly) faster algorithm for klee's measure problem (2008) (71)
All-Pairs Shortest Paths with Real Weights in O(n3/log n) Time (2005) (71)
Multi-Pass Geometric Algorithms (2005) (70)
Closest-point problems simplified on the RAM (2002) (69)
Instance-Optimal Geometric Algorithms (2009) (65)
A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections (1994) (57)
Optimizing area and aspect ration in straight-line orthogonal tree drawings (1996) (55)
Fixed-dimensional linear programming queries made easy (1996) (54)
Faster core-set constructions and data-stream algorithms in fixed dimensions (2006) (54)
On Levels in Arrangements of Curves (2000) (53)
Persistent predecessor search and orthogonal point location on the word RAM (2011) (53)
Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-Dimensional Voronoi Diagrams (1997) (52)
On Approximate Range Counting and Depth (2007) (51)
Stochastic minimum spanning trees in euclidean spaces (2011) (50)
Speeding up the Four Russians Algorithm by About One More Logarithmic Factor (2015) (49)
Towards in-place geometric algorithms and data structures (2004) (49)
Euclidean Bounded-Degree Spanning Tree Ratios (2003) (49)
A note on maximum independent sets in rectangle intersection graphs (2004) (49)
Semi-online maintenance of geometric optima and measures (2002) (48)
A Near-Linear Area Bound for Drawing Binary Trees (1999) (46)
Linear-Space Data Structures for Range Mode Query in Arrays (2011) (46)
Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings (2015) (46)
Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time (2009) (45)
Geometric Red-Blue Set Cover for Unit Squares and Related Problems (2015) (43)
A Simple Streaming Algorithm for Minimum Enclosing Balls (2006) (43)
Closest pair and the post office problem for stochastic points (2011) (42)
Balanced vertex-orderings of graphs (2005) (41)
Comparison-based time-space lower bounds for selection (2009) (41)
Well-separated pair decomposition in linear time? (2008) (41)
Dynamic subgraph connectivity with geometric applications (2002) (40)
More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems (2018) (40)
Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three (1995) (40)
Dynamic Connectivity: Connecting to Networks and Geometry (2008) (40)
A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries (2010) (39)
On levels in arrangements of lines (1998) (37)
Adaptive and Approximate Orthogonal Range Counting (2013) (37)
Streaming and dynamic algorithms for minimum enclosing balls in high dimensions (2011) (36)
A Randomized Algorithm for Online Unit Clustering (2006) (35)
How to Morph Planar Graph Drawings (2016) (34)
Self-approaching Graphs (2012) (32)
On enumerating and selecting distances (1998) (31)
Geometric Optimization Problems over Sliding Windows (2004) (30)
On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences (2003) (30)
Drawing Partially Embedded and Simultaneously Planar Graphs (2014) (29)
Remarks on k-Level Algorithms in the Plane (1999) (29)
Morphing Planar Graph Drawings with a Polynomial Number of Steps (2013) (28)
Approximation Schemes for 0-1 Knapsack (2018) (28)
Dynamic Coresets (2008) (27)
On Levels in Arrangements of Lines, Segments, Planes, and Triangles% (1998) (27)
Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry (2006) (27)
Selection and Sorting in the "Restore" Model (2014) (27)
Linear-Space Data Structures for Range Minority Query in Arrays (2012) (26)
Improved Deterministic Algorithms for Linear Programming in Low Dimensions (2016) (26)
Deterministic algorithms for 2-d convex programming and 3-d online linear programming (1997) (25)
Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time (2004) (25)
The complexity of a single face of a minkowski sum (1995) (24)
Smart-Grid Electricity Allocation via Strip Packing with Slicing (2013) (24)
An Improved Algorithm for Online Unit Clustering (2007) (24)
Dynamic Geometric Data Structures via Shallow Cuttings (2019) (22)
Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs (2018) (20)
Fun-Sort--or the chaos of unordered binary search (2004) (20)
Maximum-Weight Planar Boxes in O(n2) Time (and Better) (2014) (20)
A Space-Efficient Algorithm for Segment Intersection (2003) (20)
Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels (2014) (20)
Dynamic Orthogonal Range Searching on the RAM, Revisited (2017) (20)
Three problems about dynamic convex hulls (2011) (19)
All-pairs shortest paths for unweighted undirected graphs in o(mn) time (2006) (18)
Optimal in-place and cache-oblivious algorithms for 3-d convex hulls and 2-d segment intersection (2010) (18)
Quake Heaps: A Simple Alternative to Fibonacci Heaps (2013) (18)
Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back (2017) (18)
Fly Cheaply: On the Minimum Fuel Consumption Problem (2001) (18)
Approximating text-to-pattern Hamming distances (2020) (17)
Voronoi diagrams in n · 2o(√lg lg n) time (2007) (17)
Towards an Optimal Method for Dynamic Planar Point Location (2015) (17)
Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry (2017) (16)
Faster Approximate Diameter and Distance Oracles in Planar Graphs (2017) (16)
On levels in arrangements of curves, iii: further improvements (2008) (16)
Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations (2013) (16)
Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM (2014) (16)
An improved approximation algorithm for the discrete Fréchet distance (2018) (15)
On Guarding Orthogonal Polygons with Sliding Cameras (2016) (15)
All-Pairs Shortest Paths in Unit-Disk Graphs in Slightly Subquadratic Time (2016) (15)
On Locality-Sensitive Orderings and their Applications (2018) (15)
Orthogonal Point Location and Rectangle Stabbing Queries in 3-d (2018) (15)
Approximating the piercing number for unit-height rectangles (2005) (14)
Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set (2012) (14)
A Fully Dynamic Algorithm for Planar Width (2003) (13)
Tree Drawings Revisited (2018) (13)
Approximation Algorithms for Maximum Cliques in 3D Unit-Disk Graphs (2005) (13)
Space-Efficient Algorithms for Klee's Measure Problem (2005) (13)
Backwards Analysis of the Karger-Klein-Tarjan Algorithm for Minimum Spanning Trees (1998) (13)
Reporting curve segment intersections using restricted predicates (2000) (13)
Balanced k-colorings (2000) (12)
All-Pairs Shortest Paths in Geometric Intersection Graphs (2017) (11)
On Levels in Arrangements of Surfaces in Three Dimensions (2005) (11)
Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers (2013) (11)
Exact Algorithms and APX-Hardness Results for Geometric Set Cover (2011) (11)
Transdichotomous Results in Computational Geometry, II: Offline Search (2010) (11)
Faster Approximation Algorithms for Geometric Set Cover (2020) (10)
The Art of Shaving Logs (2013) (10)
Approximation Algorithms for Maximum Independent Set of Pseudo-Disks (2012) (10)
Two Approaches to Building Time-Windowed Geometric Data Structures (2016) (10)
Reducing 3SUM to Convolution-3SUM (2020) (10)
Subquadratic Encodings for Point Configurations (2018) (10)
Output-sensitive construction of convex hulls (1995) (9)
Succinct Indices for Path Minimum, with Applications (2017) (8)
Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection (2009) (8)
Primal Dividing and Dual Pruning: Output-Sensitive Construction of 4-d Polytopes and 3-d Voronoi Diagrams (2007) (8)
In-place 2-d nearest neighbor search (2008) (8)
More on Change-Making and Related Problems (2020) (8)
A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions (2015) (8)
Dynamic Planar Orthogonal Point Location in Sublogarithmic Time (2018) (8)
Succinct Indices for Path Minimum, with Applications to Path Reporting (2014) (8)
(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems (2021) (8)
On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures (2014) (7)
Fast String Dictionary Lookup with One Error (2015) (7)
Hopcroft’s Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees (2021) (7)
Smallest k-Enclosing Rectangle Revisited (2019) (7)
Drawing K2, n: A lower bound (2003) (7)
Random sampling, halfspace range reporting, and construction of (/spl les/k)-levels in three dimensions (1998) (6)
Improved Bounds for Drawing Trees on Fixed Points with L-Shaped Edges (2017) (6)
Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity (2018) (6)
Better Data Structures for Colored Orthogonal Range Reporting (2020) (6)
Dynamic Streaming Algorithms for Epsilon-Kernels (2016) (6)
Further Results on Colored Range Searching (2020) (6)
Deterministic APSP, Orthogonal Vectors, and More (2020) (6)
On the Succinct Representation of Equivalence Classes (2017) (6)
A Minimalist ’ s Implementation of the 3-d Divide-and-Conquer Convex Hull Algorithm (2003) (6)
Selection and Sorting in the “Restore” Model (2018) (6)
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time (2021) (5)
Dynamic Connectivity for Axis-Parallel Rectangles (2006) (5)
Computing Shapley Values in the Plane (2018) (5)
Time-Windowed Closest Pair (2015) (5)
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions (2020) (5)
Approximating the Minimum Closest Pair Distance and Nearest Neighbor Distances of Linearly Moving Points (2015) (5)
Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles (2002) (4)
More Logarithmic-factor Speedups for 3SUM, (median,+)-convolution, and Some Geometric 3SUM-hard Problems (2019) (4)
The asteroid surveying problem and other puzzles (2003) (4)
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths (2021) (4)
Curves of width one and the river shore problem (2003) (4)
Three problems about simple polygons (2006) (4)
A note on 3D orthogonal graph drawing (2005) (4)
On the bichromatic k-set problem (2008) (4)
Finding the shortest bottleneck edge in a parametric minimum spanning tree (2005) (4)
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV (2022) (4)
Range closest-pair search in higher dimensions (2019) (3)
Dynamic ham-sandwich cuts in the plane (2009) (3)
Dynamic Geometric Set Cover, Revisited (2021) (3)
Multidimensional Range Selection (2015) (3)
Faster Algorithms for Largest Empty Rectangles and Boxes (2021) (3)
Linear-Space Data Structures for Range Mode Query in Arrays (2013) (3)
Finding median in read-only memory on integer input (2015) (3)
Computing the Nearest Neighbor Transform Exactly with Only Double Precision (2012) (3)
Space-E.cient Algorithms for Computing the Convex Hull of a Simple Polygonal Line in Linear Time (2004) (3)
Proceedings of the twenty-sixth annual symposium on Computational geometry (2013) (3)
Dynamic Streaming Algorithms for ε-Kernels (2016) (3)
Optimal Partition Trees (2012) (3)
Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs (2022) (2)
Two Approaches to Building Time-Windowed Geometric Data Structures (2019) (2)
Guarding Orthogonal Art Galleries with Sliding k-Transmitters: Hardness and Approximation (2019) (2)
A fully dynamic algorithm for planar (2001) (2)
Dynamic Generalized Closest Pair: Revisiting Eppstein's Technique (2020) (2)
Point Location in Time, Voronoi Diagrams in Time, and Other Transdichotomous Results in Computational Geometry (2006) (2)
Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices (2021) (1)
Optimal Algorithms for Geometric Centers and Depth (2019) (1)
Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings (2016) (1)
Reporting Curve Segment Interse tions Using Restri ted Predi (2000) (1)
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures (2022) (1)
Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles (2019) (1)
All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error (2021) (1)
Dynamic data structures for approximate Hausdorff distance in the word RAM (2015) (1)
A Clustering-Based Approach to Kinetic Closest Pair (2016) (1)
Faster Approximate Diameter and Distance Oracles in Planar Graphs (2019) (1)
Strip Packing with Slicing (2012) (1)
Smallest k-Enclosing Rectangle Revisited (2020) (1)
Linear-Space Data Structures for Range Minority Query in Arrays (2014) (1)
Deterministic APSP , Orthogonal Vectors , and More : Quickly (2019) (1)
Maximum-Weight Planar Boxes in O(n 2 ) Time (and (2014) (1)
On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings (2021) (1)
Improved Upper and Lower Bounds for LR Drawings of Binary Trees (2019) (1)
A Clustering-Based Approach to Kinetic Closest Pair (2017) (1)
On the Change-Making Problem (2020) (1)
On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures (2015) (1)
Dynamic Colored Orthogonal Range Searching (2021) (1)
D S ] 1 M ay 2 01 4 On Hardness of Jumbled Indexing (2014) (0)
Tree Drawings Revisited (2019) (0)
Cuttings in 2D Revisited (2014) (0)
D ec 2 01 2 Necklaces , Convolutions , and X + (2014) (0)
Combinatorial Geometry and Approximation Algorithms (2012) (0)
On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k (2023) (0)
Guest Editors’ Foreword (2014) (0)
Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back (2019) (0)
Computational geometry for non-geometers: recent developments on some classical problems (2011) (0)
A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions (2016) (0)
Bichromatic Line Segment Intersection Counting in O(n sqrt(log n)) Time (2011) (0)
Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points (2021) (0)
Subquadratic-Space Query-Efficient Data Structures for Realizable Order Types (2017) (0)
2 Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings 1 . 1 Standard Cuttings (2015) (0)
On the Succinct Representation of Equivalence Classes (2016) (0)
Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size (2023) (0)
Guest Editors’ Foreword (2014) (0)
Succinct Indices for Path Minimum, with Applications (2016) (0)
Necklaces , Convolutions , and X + Y Citation (2012) (0)
On Levels in Arrangements of Surfaces in Three Dimensions (2012) (0)
Guarding Orthogonal Art Galleries with Sliding k-Transmitters: Hardness and Approximation (2018) (0)
Minimum L∞ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem (2023) (0)
Algorithms and Data Structures (2013) (0)
Title : How to Morph Planar Graph Drawings (2018) (0)
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More (2023) (0)
Drawing Partially Embedded and (2015) (0)
Corrigendum to “Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points” [Comput. Geom. 60 (2017) 2–7] (2021) (0)
Necklaces, Convolutions, and X+Y (2012) (0)
Dynamic ham-sandwich cuts in the plane Citation (2009) (0)
Computational Geometry: Theory and Applications Dynamic ham-sandwich cuts in the plane ✩ (2009) (0)

This paper list is powered by the following services:

Other Resources About Timothy M. Chan

en.wikipedia.org

What Schools Are Affiliated With Timothy M. Chan?

Timothy M. Chan is affiliated with the following schools:

Timothy M. Chan's Academic­Influence.com Rankings