Today I served as the external member on the doctoral defense of Da Wei (David) Zheng, a student of Timothy Chan at the University of Illinois. He has an impressive portfolio of recent publications on geometric data structures and geometric graph algorithms, some of which featured in his thesis, From Geometry to Graphs and Back: Geometric Range Searching and Algorithms in Structured Graphs, and in his defense talk.

  • “Hopcroft’s problem, log-star shaving, 2d fractional cascading, and decision trees” (with Timothy Chan, arXiv:2111.03744, SODA 2022, TALG 2024) concerns data structures for half-plane range searching and their applications for Hopcroft’s problem (finding a point-line incidence), 3d Euclidean minimum spanning trees, and more. There is a tradeoff between query time and space usage for this sort of range searching problem which in many of these applications should be set to roughly \(O(n^{4/3})\) space and \(O(n^{1/3})\) query time, giving roughly \(O(n^{4/3})\) time for the applications; an old lower bound of Jeff Erickson states that for a wide class of data structures, nothing better is possible. The issue is what “roughly” in these bounds translates into when you make them more precise. Another old result of Jirka Matoušek exceeds the bounds stated above by a tiny factor, of the form \(\exp O(\log^* n)\), and the new result removes this factor, leaving exactly \(O(n^{4/3})\) time. But in his defense, David asked whether maybe it might be possible to improve the time even more, by a subpolynomial factor? This would involve going beyond Erickson’s lower bound but it might be possible if only we could prove the existence of faster decision trees for the problem. If so, then we could spend some preprocessing time to search for the optimal decision trees for tiny problems and get a tiny improvement.

  • “Simplex range searching revisited: How to shave logs in multi-level data structures” (with Timothy Chan, arXiv:2210.10172 is about another speedup, in the recursive structures common in range searching, where the nodes of one range searching data structure are decorated with instances of a second data structure. This kind of recursion allows one to specify complicated ranges as intersections of simpler ranges, by using the outer structure to restrict the data to one of the simpler ranges and the inner data structure for the other. As well as for range searching, the improved data structures from this paper also apply to range stabbing, where the data is a collection of ranges (triangles, say) and the problem is to return some kind of aggregate data on the ranges that contain a query point.

  • “Semialgebraic range stabbing, ray shooting, and intersection counting in the plane” (with Timothy Chan and Pingan Chen, arXiv:2403.12303, SoCG 2024) looks at analogous range stabbing problems with ranges defined by algebraic curves of bounded description complexity. As with other kinds of range searching problems, there is a query-space tradeoff in which with quadratic space you can getZ logarithmic query time (build the arrangement of the curves and apply point location) and with linear space you can get slightly sublinear query time. If you treat the exponents of \(n\) in the space and time bounds as Cartesian coordinates (essentially using a log-log scale), you can reach any other pair of exponents on the line segment between these two extremes, by standard techniques that subdivide the problem into smaller subproblems and then solve them separately. This interpolation between the extreme exponents is optimal for the half-plane problems that the defense started with, but not for algebraic range stabbing! David finds another structure with space \(\tilde O(n^{3/2})\) and query time \(\tilde O(n^{1/4})\), below the segment between the two extremes. One of the main ideas involves subdividing the curves into pseudo-segments (curves that cross each other at most once) and a conjectured better subdivision would lead to a better data structure.

  • “Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more” (with Adam Karczmarz, arXiv:2410.12003, SODA 2025) uses separator theorems and the theory of the Vapnik–Chervonenkis dimension of metric balls to speed up algorithms for problems like finding the farthest pair of vertices, for graphs in minor-closed families.

The defense concluded with a description of unpublished work on subquadratic algorithms for the diameter of unit disk graphs. There wasn’t time to even mention some of his other work, on subdividing points into small sets by few lines (with Sariel Har-Peled, arXiv:2208.11275, SODA 2022), approximate matching (with Monika Henzinger, arXiv:2301.09217, IPCO 2023, Math. Prog. 2025), submodular optimization (with Monika Henzinger, Paul Liu, and Jan Vondrák, arXiv:2305.00122, ICALP 2023), parallel algorithms for planar graphs (with Yi-Jun Chang, arXiv:2304.07441, SODA 2024), separators in unit disk graphs (with Elfarouk Harb and Zhengcheng Huang, arXiv:2407.15980, ESA 2024), Steiner trees in planar graphs (with Chandra Chekuri, Rhea Jain, Shubhang Kulkarni,and Weihao Zhu, arXiv:2407.01904, ESA 2024), etc.

Needless to say, with so much successful research publication, the defense was a resounding success. Next, David is heading to the Institute of Science and Technology Austria near Vienna, for postdoctoral research with Monika Henzinger.

Congratulations, David!

(Discuss on Mastodon)