Timothy M. Chan

Timothy M. Chan, Bryan T. Wilkinson: Adaptive and Approximate Orthogonal Range Counting. SODA 2013: 241-251

Soroush Alamdari, Patrizio Angelini, Timothy M. Chan, Giuseppe Di Battista, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson: Morphing Planar Graph Drawings with a Polynomial Number of Steps. SODA 2013: 1656-1667

Timothy M. Chan: Optimal Partition Trees. Discrete & Computational Geometry 47(4): 661-690 (2012)

Timothy M. Chan: On Levels in Arrangements of Surfaces in Three Dimensions. Discrete & Computational Geometry 48(1): 1-18 (2012)

Timothy M. Chan, Sariel Har-Peled: Approximation Algorithms for Maximum Independent Set of Pseudo-Disks. Discrete & Computational Geometry 48(2): 373-392 (2012)

Timothy M. Chan: Three Problems about Dynamic Convex Hulls. Int. J. Comput. Geometry Appl. 22(4): 341-364 (2012)

Timothy M. Chan: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. ACM Transactions on Algorithms 8(4): 34 (2012)

Timothy M. Chan: Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set. Symposium on Computational Geometry 2012: 293-302

Soroush Alamdari, Timothy M. Chan, Elyot Grant, Anna Lubiw, Vinayak Pathak: Self-approaching Graphs. Graph Drawing 2012: 260-271

Timothy M. Chan: Combinatorial Geometry and Approximation Algorithms. ISAAC 2012: 2

David L. Millman, Steven Love, Timothy M. Chan, Jack Snoeyink: Computing the Nearest Neighbor Transform Exactly with Only Double Precision. ISVD 2012: 66-74

Timothy M. Chan, Elyot Grant, Jochen Könemann, Malcolm Sharpe: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. SODA 2012: 1576-1585

Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, Bryan T. Wilkinson: Linear-Space Data Structures for Range Mode Query in Arrays. STACS 2012: 290-301

Timothy M. Chan, Stephane Durocher, Matthew Skala, Bryan T. Wilkinson: Linear-Space Data Structures for Range Minority Query in Arrays. SWAT 2012: 295-306

David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, Perouz Taslakian: Necklaces, Convolutions, and X+Y. CoRR abs/1212.4771 (2012)

Timothy M. Chan, Mihai Patrascu, Liam Roditty: Dynamic Connectivity: Connecting to Networks and Geometry. SIAM J. Comput. 40(2): 333-349 (2011)

Timothy M. Chan, Bryan T. Wilkinson: Bichromatic Line Segment Intersection Counting in O(n sqrt(log n)) Time. CCCG 2011

Elyot Grant, Timothy M. Chan: Exact Algorithms and APX-Hardness Results for Geometric Set Cover. CCCG 2011

Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu: Orthogonal range searching on the RAM, revisited. Symposium on Computational Geometry 2011: 1-10

Timothy M. Chan: Three problems about dynamic convex hulls. Symposium on Computational Geometry 2011: 27-36

Pegah Kamousi, Timothy M. Chan, Subhash Suri: Stochastic minimum spanning trees in euclidean spaces. Symposium on Computational Geometry 2011: 65-74

Timothy M. Chan: Persistent Predecessor Search and Orthogonal point Location on the Word RAM. SODA 2011: 1131-1145

Timothy M. Chan, Vinayak Pathak: Streaming and Dynamic Algorithms for Minimum Enclosing Balls in High Dimensions. WADS 2011: 195-206

Pegah Kamousi, Timothy M. Chan, Subhash Suri: Closest Pair and the Post Office Problem for Stochastic Points. WADS 2011: 548-559

Timothy M. Chan, Sariel Har-Peled: Approximation Algorithms for Maximum Independent Set of Pseudo-Disks. CoRR abs/1103.1431 (2011)

Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu: Orthogonal Range Searching on the RAM, Revisited. CoRR abs/1103.5510 (2011)

Timothy M. Chan: A (slightly) faster algorithm for Klee's measure problem. Comput. Geom. 43(3): 243-250 (2010)

Timothy M. Chan, Eric Y. Chen: Optimal in-place and cache-oblivious algorithms for 3-d convex hulls and 2-d segment intersection. Comput. Geom. 43(8): 636-646 (2010)

Timothy M. Chan: A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. J. ACM 57(3) (2010)

Timothy M. Chan: More Algorithms for All-Pairs Shortest Paths in Weighted Graphs. SIAM J. Comput. 39(5): 2075-2089 (2010)

Timothy M. Chan: Comparison-based time-space lower bounds for selection. ACM Transactions on Algorithms 6(2) (2010)

Timothy M. Chan: On the bichromatic k-set problem. ACM Transactions on Algorithms 6(4) (2010)

Timothy M. Chan: Optimal partition trees. Symposium on Computational Geometry 2010: 1-10

Timothy M. Chan, Mihai Patrascu: Counting Inversions, Offline Orthogonal Range Counting, and Related Problems. SODA 2010: 161-173

Timothy M. Chan, Mihai Patrascu: Transdichotomous Results in Computational Geometry, II: Offline Search. CoRR abs/1010.1948 (2010)

Peyman Afshani, Timothy M. Chan: Dynamic Connectivity for Axis-Parallel Rectangles. Algorithmica 53(4): 474-487 (2009)

Hamid Zarrabi-Zadeh, Timothy M. Chan: An Improved Algorithm for Online Unit Clustering. Algorithmica 54(4): 490-500 (2009)

Timothy G. Abbott, Michael Burr, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel M. Kane, Stefan Langerman, Jelani Nelson, Eynat Rafalin, Kathryn Seyboth, Vincent Yeung: Dynamic ham-sandwich cuts in the plane. Comput. Geom. 42(5): 419-428 (2009)

Peyman Afshani, Timothy M. Chan: On Approximate Range Counting and Depth. Discrete & Computational Geometry 42(1): 3-21 (2009)

Timothy M. Chan: Dynamic Coresets. Discrete & Computational Geometry 42(3): 469-488 (2009)

Timothy M. Chan, Hamid Zarrabi-Zadeh: A Randomized Algorithm for Online Unit Clustering. Theory Comput. Syst. 45(3): 486-496 (2009)

Timothy M. Chan, Mihai Patrascu: Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time. SIAM J. Comput. 39(2): 703-729 (2009)

Timothy M. Chan, Eric Y. Chen: Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection. Symposium on Computational Geometry 2009: 80-87

Timothy M. Chan, Sariel Har-Peled: Approximation algorithms for maximum independent set of pseudo-disks. Symposium on Computational Geometry 2009: 333-340

Peyman Afshani, Jérémy Barbay, Timothy M. Chan: Instance-Optimal Geometric Algorithms. FOCS 2009: 129-138

Timothy M. Chan: Comparison-based time-space lower bounds for selection. SODA 2009: 140-149

Peyman Afshani, Timothy M. Chan: Optimal halfspace range reporting in three dimensions. SODA 2009: 180-186

Timothy M. Chan: All-Pairs Shortest Paths with Real Weights in O ( n ³/log n ) Time. Algorithmica 50(2): 236-243 (2008)

Timothy M. Chan: Well-separated pair decomposition in linear time? Inf. Process. Lett. 107(5): 138-141 (2008)

Timothy M. Chan: Dynamic coresets. Symposium on Computational Geometry 2008: 1-9

Timothy M. Chan: On levels in arrangements of curves, iii: further improvements. Symposium on Computational Geometry 2008: 85-93

Timothy M. Chan: A (slightly) faster algorithm for klee's measure problem. Symposium on Computational Geometry 2008: 94-100

Timothy M. Chan, Mihai Patrascu, Liam Roditty: Dynamic Connectivity: Connecting to Networks and Geometry. FOCS 2008: 95-104

Timothy M. Chan: On the bichromatic k-set problem. SODA 2008: 561-570

Timothy M. Chan, Eric Y. Chen: In-place 2-d nearest neighbor search. SODA 2008: 904-911

Timothy M. Chan, Mihai Patrascu, Liam Roditty: Dynamic Connectivity: Connecting to Networks and Geometry. CoRR abs/0808.1128 (2008)

Timothy M. Chan, Eric Y. Chen: Multi-Pass Geometric Algorithms. Discrete & Computational Geometry 37(1): 79-102 (2007)

Hamid Zarrabi-Zadeh, Timothy M. Chan: An Improved Algorithm for Online Unit Clustering. COCOON 2007: 383-393

Peyman Afshani, Timothy M. Chan: On approximate range counting and depth. Symposium on Computational Geometry 2007: 337-343

Timothy M. Chan, Mihai Patrascu: Voronoi diagrams in n·2^{osqrt(lg lg n)} time. STOC 2007: 31-39

Timothy M. Chan: More algorithms for all-pairs shortest paths in weighted graphs. STOC 2007: 590-598

Hervé Brönnimann, Timothy M. Chan: Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time. Comput. Geom. 34(2): 75-82 (2006)

Timothy M. Chan: Faster core-set constructions and data-stream algorithms in fixed dimensions. Comput. Geom. 35(1-2): 20-35 (2006)

Timothy M. Chan: Three problems about simple polygons. Comput. Geom. 35(3): 209-217 (2006)

Timothy M. Chan, Bashir S. Sadjad: Geometric Optimization Problems over Sliding Windows. Int. J. Comput. Geometry Appl. 16(2-3): 145-158 (2006)

Timothy M. Chan: Dynamic Subgraph Connectivity with Geometric Applications. SIAM J. Comput. 36(3): 681-694 (2006)

Hamid Zarrabi-Zadeh, Timothy M. Chan: A Simple Streaming Algorithm for Minimum Enclosing Balls. CCCG 2006

Peyman Afshani, Timothy M. Chan: Dynamic Connectivity for Axis-Parallel Rectangles. ESA 2006: 16-27

David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian: Necklaces, Convolutions, and X + Y. ESA 2006: 160-171

Timothy M. Chan: Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry. FOCS 2006: 333-344

Timothy M. Chan: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. SODA 2006: 514-523

Timothy M. Chan: A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. SODA 2006: 1196-1202

Timothy M. Chan, Hamid Zarrabi-Zadeh: A Randomized Algorithm for Online Unit Clustering. WAOA 2006: 121-131

Therese C. Biedl, Timothy M. Chan, Yashar Ganjali, Mohammad Taghi Hajiaghayi, David R. Wood: Balanced vertex-orderings of graphs. Discrete Applied Mathematics 148(1): 27-48 (2005)

Therese C. Biedl, Timothy M. Chan: A note on 3D orthogonal graph drawing. Discrete Applied Mathematics 148(2): 189-193 (2005)

Timothy M. Chan: On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences. Discrete & Computational Geometry 34(1): 11-24 (2005)

Timothy M. Chan: Low-Dimensional Linear Programming with Violations. SIAM J. Comput. 34(4): 879-893 (2005)

Timothy M. Chan, Abdullah-Al Mahmood: Approximating the piercing number for unit-height rectangles. CCCG 2005: 15-18

Peyman Afshani, Timothy M. Chan: Approximation Algorithms for Maximum Cliques in 3D Unit-Disk Graphs. CCCG 2005: 19-22

Eric Y. Chen, Timothy M. Chan: Space-Efficient Algorithms for Klee's Measure Problem. CCCG 2005: 27-30

Timothy M. Chan, Eric Y. Chen: Multi-pass geometric algorithms. Symposium on Computational Geometry 2005: 180-189

Timothy M. Chan: On levels in arrangements of surfaces in three dimensions. SODA 2005: 232-240

Timothy M. Chan: Finding the shortest bottleneck edge in a parametric minimum spanning tree. SODA 2005: 917-918

Timothy M. Chan: All-Pairs Shortest Paths with Real Weights in O(n³/log n) Time. WADS 2005: 318-324

Therese C. Biedl, Timothy M. Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai J. Golin, James A. King, J. Ian Munro: Fun-Sort--or the chaos of unordered binary search. Discrete Applied Mathematics 144(3): 231-236 (2004)

Timothy M. Chan: Euclidean Bounded-Degree Spanning Tree Ratios. Discrete & Computational Geometry 32(2): 177-194 (2004)

Timothy M. Chan: A note on maximum independent sets in rectangle intersection graphs. Inf. Process. Lett. 89(1): 19-23 (2004)

Timothy M. Chan: Faster core-set constructions and data stream algorithms in fixed dimensions. Symposium on Computational Geometry 2004: 152-159

Hervé Brönnimann, Timothy M. Chan, Eric Y. Chen: Towards in-place geometric algorithms and data structures. Symposium on Computational Geometry 2004: 239-246

Timothy M. Chan, Bashir S. Sadjad: Geometric Optimization Problems Over Sliding Windows. ISAAC 2004: 246-258

Hervé Brönnimann, Timothy M. Chan: Space-E.cient Algorithms for Computing the Convex Hull of a Simple Polygonal Line in Linear Time. LATIN 2004: 162-171

Timothy M. Chan: An optimal randomized algorithm for maximum Tukey depth. SODA 2004: 430-436

Timothy M. Chan: On Levels in Arrangements of Curves. Discrete & Computational Geometry 29(3): 375-393 (2003)

Timothy M. Chan: A Fully Dynamic Algorithm for Planar Width. Discrete & Computational Geometry 30(1): 17-24 (2003)

Therese C. Biedl, Timothy M. Chan, Alejandro López-Ortiz: Drawing K_{2, n}: A lower bound. Inf. Process. Lett. 85(6): 303-305 (2003)

Timothy M. Chan: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46(2): 178-189 (2003)

Timothy M. Chan: Semi-Online Maintenance of Geometric Optima and Measures. SIAM J. Comput. 32(3): 700-716 (2003)

Eric Y. Chen, Timothy M. Chan: A Space-Efficient Algorithm for Segment Intersection. CCCG 2003: 68-71

Timothy M. Chan, Alexander Golynski, Alejandro López-Ortiz, Claude-Guy Quimper: Curves of width one and the river shore problem. CCCG 2003: 73-75

Timothy M. Chan: Euclidean bounded-degree spanning tree ratios. Symposium on Computational Geometry 2003: 11-19

Timothy M. Chan, Alexander Golynski, Alejandro López-Ortiz, Claude-Guy Quimper: the asteroid surveying problem and other puzzles. Symposium on Computational Geometry 2003: 372-373

Timothy M. Chan: On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences. FOCS 2003: 544-550

Timothy M. Chan: A Near-Linear Area Bound for Drawing Binary Trees. Algorithmica 34(1): 1-13 (2002)

Timothy M. Chan, Michael T. Goodrich, S. Rao Kosaraju, Roberto Tamassia: Optimizing area and aspect ration in straight-line orthogonal tree drawings. Comput. Geom. 23(2): 153-162 (2002)

Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang: Balanced k-colorings. Discrete Mathematics 254(1-3): 19-32 (2002)

Timothy M. Chan: Approximating the Diameter, Width, Smallest Enclosing Cylinder, and Minimum-Width Annulus. Int. J. Comput. Geometry Appl. 12(1-2): 67-85 (2002)

Therese C. Biedl, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, Ming-wei Wang: Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles. CCCG 2002: 105-108

Therese C. Biedl, Timothy M. Chan, Alejandro López-Ortiz: Drawing k₂, n: A lower bound. CCCG 2002: 146-148

Timothy M. Chan: Low-Dimensional Linear Programming with Violations. FOCS 2002: 570-

Timothy M. Chan: Closest-point problems simplified on the RAM. SODA 2002: 472-473

Timothy M. Chan: Semi-online maintenance of geometric optima and measures. SODA 2002: 474-483

Timothy M. Chan: Dynamic subgraph connectivity with geometric applications. STOC 2002: 7-13

Timothy M. Chan: On Enumerating and Selecting Distances. Int. J. Comput. Geometry Appl. 11(3): 291-304 (2001)

Timothy M. Chan: Dynamic planar convex hull operations in near-logarithmaic amortized time. J. ACM 48(1): 1-12 (2001)

Timothy M. Chan, Alon Efrat: Fly Cheaply: On the Minimum Fuel Consumption Problem. J. Algorithms 41(2): 330-337 (2001)

Timothy M. Chan: A fully dynamic algorithm for planar. Symposium on Computational Geometry 2001: 172-176

Timothy M. Chan: Reporting curve segment intersections using restricted predicates. Comput. Geom. 16(4): 245-256 (2000)

Timothy M. Chan: Random Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions. SIAM J. Comput. 30(2): 561-575 (2000)

Timothy M. Chan: Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. Symposium on Computational Geometry 2000: 300-309

Timothy M. Chan: On Levels in Arrangements of Curves. FOCS 2000: 219-227

Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang: Balanced k-Colorings. MFCS 2000: 202-211

Timothy M. Chan: More planar two-center algorithms. Comput. Geom. 13(3): 189-198 (1999)

Timothy M. Chan: Geometric Applications of a Randomized Optimization Technique. Discrete & Computational Geometry 22(4): 547-567 (1999)

Timothy M. Chan: Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time. FOCS 1999: 92-99

Timothy M. Chan: A Near-Linear Area Bound for Drawing Binary Trees. SODA 1999: 161-168

Pankaj K. Agarwal, Boris Aronov, Timothy M. Chan, Micha Sharir: On Levels in Arrangements of Lines, Segments, Planes, and Triangles%. Discrete & Computational Geometry 19(3): 315-331 (1998)

Timothy M. Chan: Approximate Nearest Neighbor Queries Revisited. Discrete & Computational Geometry 20(3): 359-373 (1998)

Timothy M. Chan: Backwards Analysis of the Karger-Klein-Tarjan Algorithm for Minimum Spanning. Inf. Process. Lett. 67(6): 303-304 (1998)

Timothy M. Chan: Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming. J. Algorithms 27(1): 147-166 (1998)

Timothy M. Chan: Geometric Applications of a Randomized Optimization Technique. Symposium on Computational Geometry 1998: 269-278

Timothy M. Chan: On Enumerating and Selecting Distances. Symposium on Computational Geometry 1998: 279-286

Timothy M. Chan: Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions. FOCS 1998: 586-595

Timothy M. Chan, Jack Snoeyink, Chee-Keng Yap: Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-Dimensional Voronoi Diagrams. Discrete & Computational Geometry 18(4): 433-454 (1997)

Timothy M. Chan: Approximate Nearest Neighbor Queries Revisited. Symposium on Computational Geometry 1997: 352-358

Timothy M. Chan: Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming. SODA 1997: 464-472

Timothy M. Chan: Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions. Discrete & Computational Geometry 16(4): 361-368 (1996)

Timothy M. Chan: Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems. Discrete & Computational Geometry 16(4): 369-387 (1996)

Timothy M. Chan: Fixed-Dimensional Linear Programming Queries Made Easy. Symposium on Computational Geometry 1996: 284-290

Timothy M. Chan, Michael T. Goodrich, S. Rao Kosaraju, Roberto Tamassia: Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings. Graph Drawing 1996: 63-75

Timothy M. Chan: Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems. Symposium on Computational Geometry 1995: 10-19

Timothy M. Chan, Jack Snoeyink, Chee-Keng Yap: Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three. SODA 1995: 282-291

Timothy M. Chan: A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections. CCCG 1994: 263-268