The School of Computer Science is pleased to present…
Date: Thursday, May 1st, 2025
Time: 11:00 AM
Location: Essex Hall, Room 122
Introduced by Biedl, Biniaz, and Lubiw (CCCG 2019), the minimum ply covering of a point set P with a set S of geometric objects in the plane asks for a subset S ′ of S that covers all points of P while minimizing the maximum number of overlapping objects at any point in the plane (not only at points of P). This problem is NP-hard and cannot be approximated by a factor better than 2. Biedl et al. studied this problem for objects that are unit squares or unit disks. They present 2-approximation algorithms that run in polynomial time when the optimum objective value is bounded by a constant. We generalize this result and obtain a 2-approximation algorithm for any fixed-size convex shape. The new algorithm also runs in polynomial time if the optimum objective value is bounded.
Internal Reader: Dr. Curtis Bright
External Reader: Dr. Mehdi Sangani Monfared
Advisor: Dr. Ahmad Biniaz