{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/129412"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/129412","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"From geometry to graphs and back: Geometric range searching and algorithms in structured graphs","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","abstract_has_math":false,"creators":["Zheng, Da Wei"],"institution":"University of Illinois Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Chan, Timothy M.","Chekuri, Chandra","Har-Peled, Sariel","Eppstein, David"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-04-22","date_published":"2025-04-22","updated_at":"2026-07-22T22:25:05Z","subjects":["geometry","graph","algorithms","data structures","planar graphs"],"languages":["en","eng"],"rights":["Copyright 2025 Da Wei Zheng."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/129412","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chan, Timothy M.","Chekuri, Chandra","Har-Peled, Sariel","Eppstein, David"]},{"key":"dc:creator","label":"Author","values":["Zheng, Da Wei"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-04-22","2025-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["geometry","graph","algorithms","data structures","planar graphs"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Da Wei Zheng."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/129412"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","The student, Da Wei Zheng, accepted the attached license on 2025-04-18 at 17:13.","The student, Da Wei Zheng, submitted this Dissertation for approval on 2025-04-18 at 17:31.","This Dissertation was approved for publication on 2025-04-22 at 08:59.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21840 on 2025-10-19 at 18:18:27","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["From geometry to graphs and back: Geometric range searching and algorithms in structured graphs"]}]}],"canonical_facts":{"dc:contributor":["Chan, Timothy M.","Chekuri, Chandra","Har-Peled, Sariel","Eppstein, David"],"dc:creator":["Zheng, Da Wei"],"dc:date":["2025-04-22","2025-05"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","The student, Da Wei Zheng, accepted the attached license on 2025-04-18 at 17:13.","The student, Da Wei Zheng, submitted this Dissertation for approval on 2025-04-18 at 17:31.","This Dissertation was approved for publication on 2025-04-22 at 08:59.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21840 on 2025-10-19 at 18:18:27","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/129412"],"dc:language":["en","eng"],"dc:rights":["Copyright 2025 Da Wei Zheng."],"dc:subject":["geometry","graph","algorithms","data structures","planar graphs"],"dc:title":["From geometry to graphs and back: Geometric range searching and algorithms in structured graphs"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:05Z"}