Minimum Ply Covering of Points with Convex Shapes - MSc Thesis Proposal by: Zhikai Lin

Thursday, May 1, 2025 - 11:00

The School of Computer Science is pleased to present…

 

Minimum Ply Covering of Points with Convex Shapes:
MSc Thesis Proposal by: Zhikai Lin

 

Date: Thursday, May 1st, 2025

Time: 11:00 AM

Location: Essex Hall, Room 122

 

Abstract:

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.

Thesis Committee:

Internal Reader: Dr. Curtis Bright

External Reader: Dr. Mehdi Sangani Monfared

Advisor:  Dr. Ahmad Biniaz

            

Registration Link (only MAC students need to pre-register)