About

Timothy Moon-Yew Chan is a Founder Professor in Engineering at the University of Illinois Urbana-Champaign, affiliated with the Siebel School of Computing and Data Science within The Grainger College of Engineering. His research areas include Theory and Algorithms, with recent courses taught covering topics such as algorithms, computational geometry, randomized algorithms, and advanced data structures. He is involved in teaching and research that focus on fundamental aspects of computer science, particularly in algorithms and computational theory. His contributions are recognized within the academic community, and he is actively engaged in the educational mission of the institution, contributing to the development of computing and data science education at Illinois.

Research topics

• Combinatorics
• Discrete mathematics
• Statistics
• Mathematics
• Algorithm

Selected publications

• Derandomizing Pseudopolynomial Algorithms for Subset Sum

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapter1st authorCorresponding

  We reexamine the classical subset sum problem: given a set \(X\) of \(n\) positive integers and a number \(t\), decide whether there exists a subset of \(X\) that sums to \(t\); or more generally, compute the set out of all numbers \(y \in \{0,\ldots,t\}\) for which there exists a subset of \(X\) that sums to \(y\). Standard dynamic programming solves the problem in \(O(tn)\) time. In SODA’17, two papers appeared giving the current best deterministic and randomized algorithms, ignoring polylogarithmic factors: Koiliaris and Xu’s deterministic algorithm runs in \(\widetilde{O}(t\sqrt{n})\) time, while Bringmann’s randomized algorithm runs in \(\widetilde{O}(t)\) time. We present the first deterministic algorithm running in \(\widetilde{O}(t)\) time.

  PublisherDOI

• Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-And-Bifurcate Technique

  ArXiv.org · 2025-01-01

  articleOpen access1st authorCorresponding

  In a series of papers, Avraham, Filtser, Kaplan, Katz, and Sharir (SoCG'14), Kaplan, Katz, Saban, and Sharir (ESA'23), and Katz, Saban, and Sharir (ESA'24) studied a class of geometric optimization problems -- including reverse shortest path in unweighted and weighted unit-disk graphs, discrete Fréchet distance with one-sided shortcuts, and reverse shortest path in visibility graphs on 1.5-dimensional terrains -- for which standard parametric search does not work well due to a lack of efficient parallel algorithms for the corresponding decision problems. The best currently known algorithms for all the above problems run in $O^*(n^{6/5})=O^*(n^{1.2})$ time (ignoring subpolynomial factors), and they were obtained using a technique called \emph{shrink-and-bifurcate}. We improve the running time to $\tilde{O}(n^{8/7}) \approx O(n^{1.143})$ for these problems. Furthermore, specifically for reverse shortest path in unweighted unit-disk graphs, we improve the running time further to $\tilde{O}(n^{9/8})=\tilde{O}(n^{1.125})$.

  PublisherOA PDFDOI

• Sparse Bounded Hop-Spanners for Geometric Intersection Graphs

  ArXiv.org · 2025-04-08

  preprintOpen access

  We present new results on $2$- and $3$-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for $2$- and $3$-hop spanners for many geometric intersection graphs in $\mathbb{R}^d$. For example, we show that the intersection graph of $n$ balls in $\mathbb{R}^d$ admits a $2$-hop spanner of size $O^*\left(n^{\frac{3}{2}-\frac{1}{2(2\lfloor d/2\rfloor +1)}}\right)$ and the intersection graph of $n$ fat axis-parallel boxes in $\mathbb{R}^d$ admits a $2$-hop spanner of size $O(n \log^{d+1}n)$. Furthermore, we show that the intersection graph of general semi-algebraic objects in $\mathbb{R}^d$ admits a $3$-hop spanner of size $O^*\left(n^{\frac{3}{2}-\frac{1}{2(2D-1)}}\right)$, where $D$ is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in $\mathbb{R}^3$), we provide a lower bound of $Ω(n^{\frac{4}{3}})$. For $3$-hop and axis-parallel boxes in $\mathbb{R}^d$, we provide the upper bound $O(n \log ^{d-1}n)$ and lower bound $Ω\left(n (\frac{\log n}{\log \log n})^{d-2}\right)$.

  PublisherOA PDFDOI

• S5392 A Rare Presentation of Asymmetrical Jaundice

  The American Journal of Gastroenterology · 2025-10-01

  article1st authorCorresponding

  Introduction: Jaundice is a systemic sign of elevated serum bilirubin that typically presents in a widespread, symmetrical distribution; here, we describe an atypical case of asymmetrical jaundice with associated edema in a young cirrhotic male patient. Case Description/Methods: A 31-year-old man with a history of alcohol use, hepatitis C cirrhosis, and polysubstance abuse was admitted to the intensive care unit for management of toxic metabolic encephalopathy, gram-negative bacteremia, kidney failure, and shock. He was found to have a distended abdomen with large ascites; paracentesis was performed on the first and third day of admission, both in the right lower quadrant of his abdomen. On day 4 of admission, he was found to have more pronounced pitting edema in his left extremities compared to his right. He also had jaundice involving his entire torso and left side; however, his right arm and his entire right lower extremity were spared from both jaundice and edema. His bilirubin increased from 13.1 mg/dL from admission to 21.8 mg/dL by day 5. His pattern of asymmetrical jaundice and edema persisted until he passed away on the eighth day of admission. Discussion: To our knowledge, there have only been 2 cases of non-transient asymmetrical jaundice described in the literature, both reported before 1972. They described similar cases of cirrhotic males who developed asymmetrical jaundice and edema days after receiving a right-sided invasive procedure (portacaval shunt, paracentesis). They hypothesized that invasive intra-abdominal procedures could form a peritoneal-subcutaneous fistula that allows for ascitic fluid to enter the subcutaneous space. There, it can disseminate in an unpredictable fashion, causing both edema and jaundice within the same, asymmetrical distribution. Although this hypothesis may explain why our patients had asymmetrical edema, it assumes that the ascitic fluid should be bilirubin-rich to explain the jaundiced appearance. The normal range of ascitic bilirubin is 0.7 to 0.8 mg/dL, but elevated levels could represent choleperitoneum or a compromised bile duct. Unfortunately, this cannot be confirmed since ascitic bilirubin levels were not collected. Although this appears to be exceedingly rare, we urge those who encounter asymmetrical jaundice to further explore this unusual phenomenon and be mindful of potential clinical implications regarding biliary leaks.

  PublisherDOI

• Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01 · 3 citations

  book-chapterSenior author

  We develop simple and general techniques to obtain faster (near-linear time) static approximation algorithms, as well as efficient dynamic data structures, for four fundamental geometric optimization problems: minimum piercing set (MPS), maximum independent set (MIS), minimum vertex cover (MVC), and maximum-cardinality matching (MCM). Highlights of our results include the following:

  PublisherDOI

• Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension

  ArXiv.org · 2025-10-18

  preprintOpen access1st authorCorresponding

  We give the first truly subquadratic time algorithm, with $O^*(n^{2-1/18})$ running time, for computing the diameter of an $n$-vertex unit-disk graph, resolving a central open problem in the literature. Our result is obtained as an instance of a general framework, applicable to different graph families and distance problems. Surprisingly, our framework completely bypasses sublinear separators (or $r$-divisions) which were used in all previous algorithms. Instead, we use low-diameter decompositions in their most elementary form. We also exploit bounded VC-dimension of set systems associated with the input graph, as well as new ideas on geometric data structures. Among the numerous applications of the general framework, we obtain: 1. An $\tilde{O}(mn^{1-1/(2d)})$ time algorithm for computing the diameter of $m$-edge sparse unweighted graphs with constant VC-dimension $d$. The previously known algorithms by Ducoffe, Habib, and Viennot [SODA 2019] and Duraj, Konieczny, and Potȩpa [ESA 2024] are truly subquadratic only when the diameter is a small polynomial. Our result thus generalizes truly subquadratic time algorithms known for planar and minor-free graphs (in fact, it slightly improves the previous time bound for minor-free graphs). 2. An $\tilde{O}(n^{2-1/12})$ time algorithm for computing the diameter of intersection graphs of axis-aligned squares with arbitrary size. The best-known algorithm by Duraj, Konieczny, and Potȩpa [ESA 2024] only works for unit squares and is only truly subquadratic in the low-diameter regime. 3. The first algorithms with truly subquadratic complexity for other distance-related problems, including all-vertex eccentricities, Wiener index, and exact distance oracles. (... truncated to meet the arXiv abstract requirement.)

  PublisherOA PDFDOI

• Dynamic Independent Set of Disks (and Hypercubes) Made Easier

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01

  book-chapterSenior author

  Maintaining an approximate maximum independent set of a dynamic collection of objects has been studied extensively in the past few years. Recently, Bhore, Nöllenburg, Tóth, and Wulms (SoCG 2024) showed that for (unweighted) disks in the plane, it is possible to maintain O (1)-factor approximate solution in polylogarithmic amortized update time. In this work, we provide a much simpler dynamic O (1)-approximation algorithm, which at the same time improves the number of logarithmic factors in the previous update time bound.

  PublisherDOI

• Dynamic Geometric Set Cover, Revisited

  SIAM Journal on Computing · 2025-06-05

  article1st authorCorresponding
  PublisherDOI

• Simpler Reductions from Exact Triangle

  Society for Industrial and Applied Mathematics eBooks · 2024-01-01 · 1 citations

  book-chapter1st authorCorresponding

  In this paper, we provide simpler reductions from Exact Triangle to two important problems in fine-grained complexity: Exact Triangle with Few Zero-Weight 4-Cycles and All-Edges Sparse Triangle.

  PublisherDOI

• Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane

  arXiv (Cornell University) · 2024-01-01

  preprintOpen access1st authorCorresponding

  Polynomial partitioning techniques have recently led to improved geometric data structures for a variety of fundamental problems related to semialgebraic range searching and intersection searching in 3D and higher dimensions (e.g., see [Agarwal, Aronov, Ezra, and Zahl, SoCG 2019; Ezra and Sharir, SoCG 2021; Agarwal, Aronov, Ezra, Katz, and Sharir, SoCG 2022]). They have also led to improved algorithms for offline versions of semialgebraic range searching in 2D, via lens-cutting [Sharir and Zahl (2017)]. In this paper, we show that these techniques can yield new data structures for a number of other 2D problems even for online queries: 1) Semialgebraic range stabbing. We present a data structure for n semialgebraic ranges in 2D of constant description complexity with O(n^{3/2+ε}) preprocessing time and space, so that we can count the number of ranges containing a query point in O(n^{1/4+ε}) time, for an arbitrarily small constant ε > 0. (The query time bound is likely close to tight for this space bound.) 2) Ray shooting amid algebraic arcs. We present a data structure for n algebraic arcs in 2D of constant description complexity with O(n^{3/2+ε}) preprocessing time and space, so that we can find the first arc hit by a query (straight-line) ray in O(n^{1/4+ε}) time. (The query bound is again likely close to tight for this space bound, and they improve a result by Ezra and Sharir with near n^{3/2} space and near √n query time.) 3) Intersection counting amid algebraic arcs. We present a data structure for n algebraic arcs in 2D of constant description complexity with O(n^{3/2+ε}) preprocessing time and space, so that we can count the number of intersection points with a query algebraic arc of constant description complexity in O(n^{1/2+ε}) time. In particular, this implies an O(n^{3/2+ε})-time algorithm for counting intersections between two sets of n algebraic arcs in 2D. (This generalizes a classical O(n^{3/2+ε})-time algorithm for circular arcs by Agarwal and Sharir from SoCG 1991.)

  PublisherOA PDFDOI

Recent grants

• AF: Small: Computational Geometry from a Fine-Grained Perspective

  NSF · $600k · 2022–2026

• AF: Small: Fundamental Problems in Geometric Data Structures

  NSF · $500k · 2018–2021

Frequent coauthors

• Sariel Har-Peled

  University of Illinois Urbana-Champaign

  23 shared

• Bryan T. Wilkinson

  Aarhus University

  21 shared

• Thérèse Biedl

  19 shared

• Qizheng He

  University of Illinois Urbana-Champaign

  15 shared

• Anna Lubiw

  15 shared

• Peyman Afshani

  Aarhus University

  13 shared

• Mihai Pătraşcu

  11 shared

• Konstantinos Tsakalidis

  University of Liverpool

  11 shared

Education

• Ph.D., Computer Science

  University of Illinois at Urbana-Champaign

  2005

• M.S., Computer Science

  University of Illinois at Urbana-Champaign

  2001

• B.S., Computer Science

  National University of Singapore

  1998

Awards & honors

• Illinois CS Places 28 Faculty on CITL List of Teachers Ranke…
• Honored by ACM