The School of Computer Science is pleased to present…
Minimizing Ply and Membership in Geometric Covering Problems
MSc Thesis Defense by: Zhikai Lin
Date: Wednesday, August 6th, 2025
Time: 1:00 pm
Location: Essex Hall, Room 122
This thesis studies two variants of geometric set cover problems: the Minimum Ply Geometric Set Cover (MPGSC) and the Minimum Membership Geometric Set Cover (MMGSC). For the MPGSC problem, we present a 2-approximation algorithm for points covered by translated copies of a fixed-size convex polygon. This algorithm generalizes the previous approach of Biedl et al. for unit squares and disks. It runs in O(|C| * (L+n) * m^(12L+1)) time when the optimal ply is bounded by a constant L, where n is the number of points, m is the number of objects, and |C| is the number of vertices of the convex polygon. For the MMGSC problem, we present an exact polynomial-time algorithm for points covered by half-planes. This algorithm, which is similar to the sweep-line algorithm used by Erlebach and van Leeuwen for the Minimum Membership Set Cover problem with unit squares, finds a solution whose maximum membership is precisely the optimal value. It runs in O (n^2 * m^(4L+4)) time, assuming the optimal membership is bounded by a constant L.
Internal Reader: Dr. Curtis Bright
External Reader: Dr. Mehdi S. Monfared
Advisor: Dr. Ahmad Biniaz
Chair: Dr. Dan Wu