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

Zheng, Da Wei

Permalink

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

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