Login | Register

The local covering problem: producing and certifying local coverings

Title:

The local covering problem: producing and certifying local coverings

van der Valk Bouman, Jim (2020) The local covering problem: producing and certifying local coverings. Masters thesis, Concordia University.

[thumbnail of vanderValkBouman_MSc-F2020.pdf]
Preview
Text (application/pdf)
vanderValkBouman_MSc-F2020.pdf - Accepted Version
600kB

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.

Divisions:Concordia University > Faculty of Arts and Science > Mathematics and Statistics
Item Type:Thesis (Masters)
Authors:van der Valk Bouman, Jim
Institution:Concordia University
Degree Name:M. Sc.
Program:Mathematics
Date:13 July 2020
Thesis Supervisor(s):Rosso, Giovanni and Lipnowski, Michael
ID Code:987429
Deposited By: Jim van der Valk Bouman
Deposited On:25 Nov 2020 16:18
Last Modified:25 Nov 2020 16:18
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top