Abstract

The covering problem is a classical type of problem that is concerned with finding the smallest collection of structures such that a larger structure is covered. In this thesis we focus on a few examples of the local covering problem, which can be described by the following goal:

Given a connected set X on a manifold and a fixed r>0, find the smallest set of points such that the union of the balls of radius r around the points covers X.

We first explore the problem by picking a few easier settings and constructing an algorithm that can explicitly produce coverings of a certain set. We then discuss a result in algebraic topology based on the construction of the nerve of a covering, which allows us to certify that a given collection of opens provides a covering of the set. This inherently interesting result allows us to finally improve on the results of our algorithm. We do this by removing some points from its output configurations and applying gradient flow to move them around such that they repel each other. We then apply the homological criterion to verify that the points give a covering after gradient flow, in which case we have improved our results.