Geometric set cover and related geometric optimization problems

He, Qizheng

Permalink

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

Description

Title

Geometric set cover and related geometric optimization problems

Author(s)

He, Qizheng

Issue Date

2023-09-11

Director of Research (if dissertation) or Advisor (if thesis)

Chan, Timothy M.

Doctoral Committee Chair(s)

Chan, Timothy M.

Committee Member(s)

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

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• geometric set cover
• approximation algorithms
• dynamic data structures

Abstract

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}$.

Graduation Semester

2023-12

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Qizheng He

Owning Collections