{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/121941"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/121941","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Geometric set cover and related geometric optimization problems","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms","abstract_has_math":false,"creators":["He, Qizheng"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Chan, Timothy M.","Har-Peled, Sariel","Chekuri, Chandra","Agarwal, Pankaj K."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-12","date_published":"2023-12","updated_at":"2026-07-22T22:25:00Z","subjects":["Geometric Set Cover","Approximation Algorithms","Dynamic Data Structures"],"languages":["en","eng"],"rights":["Copyright 2023 Qizheng He"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/121941","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chan, Timothy M.","Har-Peled, Sariel","Chekuri, Chandra","Agarwal, Pankaj K."]},{"key":"dc:creator","label":"Author","values":["He, Qizheng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-12","2023-09-11"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"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 at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Geometric Set Cover","Approximation Algorithms","Dynamic Data Structures"]}]},{"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 2023 Qizheng He"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/121941"]}]},{"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 2024-03-01 without embargo terms","The student, Qizheng He, accepted the attached license on 2023-09-08 at 04:40.","The student, Qizheng He, submitted this Dissertation for approval on 2023-09-08 at 04:50.","This Dissertation was approved for publication on 2023-09-11 at 15:50.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19821 on 2024-03-01 at 13:13:22","Geometric set cover is a classical problem in computational geometry, with a long history and many applications. Given a set $X$ of points in $\\mathbb{R}^d$ and a set $S$ of geometric objects, the problem asks to find a smallest subset of objects from $S$ that covers all points in $X$. In this thesis, we study algorithms, data structures and hardness results for geometric set cover and other related geometric optimization problems. In the first part, we focus on static geometric set cover, where all points and objects are given in advance. As the problem is NP-hard for many classes of geometric objects, we are interested in designing $O(1)$-approximation algorithms, in particular, efficient algorithms that run in near-linear time. For the unweighted problem, we present near-optimal deterministic and randomized algorithms for 2D disks and 3D halfspaces, which are further improved to optimal $O(n\\log n)$ time in the next part. We then extend our approach to solve the weighted problem for the same types of ranges, in also near-linear time. In the second part, we explore geometric set cover problems in dynamic settings, allowing insertions and deletions of both points and objects. The goal is to efficiently maintain a set cover solution (satisfying certain quality requirement) for the dynamic problem instance. We give a plethora of new dynamic geometric set cover data structures for various geometric ranges in 1D, 2D and 3D, which significantly improve and extend the previous results. We also give the first sublinear results for the weighted version of the problem. In the third part, we investigate the fine-grained complexity of the discrete $k$-center problem and related (exact) geometric set cover problems when $k$ or the size of the cover is small. We give the first subquadratic algorithms for unweighted and weighted size-3 set cover for rectangles in $\\mathbb{R}^2$, and also prove conditional lower bounds for these problems in constant dimensions. In the fourth part, we develop approximation algorithms for another problem related to geometric set cover, namely, enclosing points with geometric objects. We solve this problem by adapting techniques for approximating geometric set cover. In the last part, we inspect the FPT status of the monotone convex chain cover problem, where the problem asks for finding the minimum number of $x$-monotone convex chains $\\kappa(P)$ that can together cover a point set $P$. We show that deciding whether $\\kappa(P)\\leq k$ is NP-hard and does not have a polynomial kernel, unless $\\mathrm{NP}\\subseteq \\mathrm{coNP/poly}$."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Geometric set cover and related geometric optimization problems"]}]}],"canonical_facts":{"dc:contributor":["Chan, Timothy M.","Har-Peled, Sariel","Chekuri, Chandra","Agarwal, Pankaj K."],"dc:creator":["He, Qizheng"],"dc:date":["2023-12","2023-09-11"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms","The student, Qizheng He, accepted the attached license on 2023-09-08 at 04:40.","The student, Qizheng He, submitted this Dissertation for approval on 2023-09-08 at 04:50.","This Dissertation was approved for publication on 2023-09-11 at 15:50.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19821 on 2024-03-01 at 13:13:22","Geometric set cover is a classical problem in computational geometry, with a long history and many applications. Given a set $X$ of points in $\\mathbb{R}^d$ and a set $S$ of geometric objects, the problem asks to find a smallest subset of objects from $S$ that covers all points in $X$. In this thesis, we study algorithms, data structures and hardness results for geometric set cover and other related geometric optimization problems. In the first part, we focus on static geometric set cover, where all points and objects are given in advance. As the problem is NP-hard for many classes of geometric objects, we are interested in designing $O(1)$-approximation algorithms, in particular, efficient algorithms that run in near-linear time. For the unweighted problem, we present near-optimal deterministic and randomized algorithms for 2D disks and 3D halfspaces, which are further improved to optimal $O(n\\log n)$ time in the next part. We then extend our approach to solve the weighted problem for the same types of ranges, in also near-linear time. In the second part, we explore geometric set cover problems in dynamic settings, allowing insertions and deletions of both points and objects. The goal is to efficiently maintain a set cover solution (satisfying certain quality requirement) for the dynamic problem instance. We give a plethora of new dynamic geometric set cover data structures for various geometric ranges in 1D, 2D and 3D, which significantly improve and extend the previous results. We also give the first sublinear results for the weighted version of the problem. In the third part, we investigate the fine-grained complexity of the discrete $k$-center problem and related (exact) geometric set cover problems when $k$ or the size of the cover is small. We give the first subquadratic algorithms for unweighted and weighted size-3 set cover for rectangles in $\\mathbb{R}^2$, and also prove conditional lower bounds for these problems in constant dimensions. In the fourth part, we develop approximation algorithms for another problem related to geometric set cover, namely, enclosing points with geometric objects. We solve this problem by adapting techniques for approximating geometric set cover. In the last part, we inspect the FPT status of the monotone convex chain cover problem, where the problem asks for finding the minimum number of $x$-monotone convex chains $\\kappa(P)$ that can together cover a point set $P$. We show that deciding whether $\\kappa(P)\\leq k$ is NP-hard and does not have a polynomial kernel, unless $\\mathrm{NP}\\subseteq \\mathrm{coNP/poly}$."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/121941"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Qizheng He"],"dc:subject":["Geometric Set Cover","Approximation Algorithms","Dynamic Data Structures"],"dc:title":["Geometric set cover and related geometric optimization problems"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:00Z"}