Geometric set cover and related geometric optimization problems

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}², 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 NP\subseteq coNP/poly.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• He, Qizheng

Contributors dc:contributor

• Chan, Timothy M.
• Har-Peled, Sariel
• Chekuri, Chandra
• Agarwal, Pankaj K.

• Geometric Set Cover
• Approximation Algorithms
• Dynamic Data Structures

Statement dc:rights

• Copyright 2023 Qizheng He

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

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