Date of Award
May 2016
Degree Type
Dissertation
Degree Name
Doctor of Philosophy
Department
Engineering
First Advisor
Adrian Dumitrescu
Committee Members
Christine Cheng, Chiu-Tai Law, Jeb Willenbring, Guangwu Xu
Keywords
Algorithm, Fence Patrolling, Geometric Spanner, Polygon Cutting
Abstract
The purpose of this dissertation is to study problems that lie at the intersection of geometry and computer science. We have studied and obtained several results from three different areas, namely–geometric spanners, polygon cutting, and fence patrolling. Specifically, we have designed and analyzed algorithms along with various combinatorial results in these three areas. For geometric spanners, we have obtained combinatorial results regarding lower bounds on worst case dilation of plane spanners. We also have studied low degree plane lattice spanners, both square and hexagonal, of low dilation. Next, for polygon cutting, we have designed and analyzed algorithms for cutting out polygon collections drawn on a piece of planar material
using the three geometric models of saw, namely, line, ray and segment cuts. For fence patrolling, we have designed several strategies for robots patrolling both open and closed fences.
Recommended Citation
Ghosh, Anirban, "Algorithmic and Combinatorial Results on Fence Patrolling, Polygon Cutting and Geometric Spanners" (2016). Theses and Dissertations. 1142.
https://dc.uwm.edu/etd/1142