Date of Award

May 2016

Degree Type


Degree Name

Doctor of Philosophy



First Advisor

Adrian Dumitrescu

Committee Members

Christine Cheng, Chiu-Tai Law, Jeb Willenbring, Guangwu Xu


Algorithm, Fence Patrolling, Geometric Spanner, Polygon Cutting


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.