From geometry to graphs and back: Geometric range searching and algorithms in structured graphs

The thesis has two parts. The first part is on geometric data structures related to range searching with linear ranges whose boundaries consists of lines or line segments, and semi-algebraic ranges whose boundaries can be described by algebraic equations. These data structures are fundamental components of geometric algorithms such as for nearest neighbors, Euclidean minimum spanning tree, and computing Voronoi diagrams. These problems reduce to solving an offline data structure problem involving n points and n ranges. In this regime, we show that an algorithm running in O(n^4/3) time exists, which match existing lower bounds. We also study the extremes of the data structure tradeoff for when the number of points is much larger than the number of ranges, and vice versa, and provide improved bounds for simplex ranges in these extremes. Additionally, we consider the dual problem of range stabbing, where a set of ranges are preprocessed, and we wish to report information about the ranges stabbed by a query point. For semi-algebraic ranges, we give improved data structure tradeoffs for range stabbing that avoid dependence in the exponent on the complexity of the semi-algebraic ranges. In addition, the aforementioned results all lead to improved algorithms for handling line segment (or algebraic arc) intersections. The second part of the thesis is focused on developing algorithms for structured classes of graphs such as planar graphs, minor-free graphs, and geometric intersection graphs. There are many algorithmic questions that are provably difficult to do in general graphs, but are possible if we assume some additional structural properties. For planar graphs, we show that in the massively parallel model of computation, problems like computing connected components, approximate shortest paths, and approximate flows and cuts, can be computed in constantly many rounds. For minor-free graph families, we use techniques involving VC- dimension to show that subquadratic time algorithms for computing diameter, eccentricity, and Weiner index exist, as well as subquadratic space distance oracles with logarithmic query time exist. These results hold for unweighted directed graphs, and our distance oracle results even extend to directed graphs with real edge weights. For geometric intersection graphs, we show that a truly subquadratic time algorithm for computing the diameter in unit-disk graph exists. This was an open question that was repeatedly asked, in light of conditional lower bounds that rule out subquadratic time algorithms for intersection graphs of spheres in three dimensions, or even for unit line segments in the plane. The algorithm we present involves an involved combination of techniques including: low diameter decompositions of graphs, VC-dimension, and geometric range searching data structures.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Zheng, Da Wei

Contributors dc:contributor

• Chan, Timothy M.
• Chekuri, Chandra
• Har-Peled, Sariel
• Eppstein, David

• geometry
• graph
• algorithms
• data structures
• planar graphs

Statement dc:rights

• Copyright 2025 Da Wei Zheng.

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129412

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129412