Withdraw
Loading…
From geometry to graphs and back: Geometric range searching and algorithms in structured graphs
Zheng, Da Wei
Loading…
Permalink
https://hdl.handle.net/2142/129412
Description
- Title
- From geometry to graphs and back: Geometric range searching and algorithms in structured graphs
- Author(s)
- Zheng, Da Wei
- Issue Date
- 2025-04-22
- Director of Research (if dissertation) or Advisor (if thesis)
- Chan, Timothy M.
- Doctoral Committee Chair(s)
- Chan, Timothy M.
- Committee Member(s)
- Chekuri, Chandra
- Har-Peled, Sariel
- Eppstein, David
- Department of Study
- Siebel School Comp & Data Sci
- Discipline
- Computer Science
- Degree Granting Institution
- University of Illinois Urbana-Champaign
- Degree Name
- Ph.D.
- Degree Level
- Dissertation
- Keyword(s)
- geometry
- graph
- algorithms
- data structures
- planar graphs
- Abstract
- 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.
- Graduation Semester
- 2025-05
- Type of Resource
- Thesis
- Handle URL
- https://hdl.handle.net/2142/129412
- Copyright and License Information
- Copyright 2025 Da Wei Zheng.
Owning Collections
Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at IllinoisManage Files
Loading…
Edit Collection Membership
Loading…
Edit Metadata
Loading…
Edit Properties
Loading…
Embargoes
Loading…