Dissertations, Theses, and Capstone Projects

Date of Degree

5-2015

Document Type

Dissertation

Degree Name

Ph.D.

Program

Computer Science

Advisor

Peter Brass

Subject Categories

Mathematics

Keywords

Approximation Algorithms; Combinatorics; Computational Geometry; Discrete Geometry; Packing Problem

Abstract

The first part of this thesis investigates combinatorial and algorithmic aspects of geometric separation problems in the plane. In such a setting one is given a set of points and a set of separators such as lines, line segments or disks. The goal is to select a small subset of those separators such that every path between any two points is intersected by at least one separator. We first look at several problems which arise when one is given a set of points and a set of unit disks embedded in the plane and the goal is to separate the points using a small subset of the given disks. Next, we focus on a separation problem involving only one region: Given a region in the plane, bounded by a piecewise linear closed curve, such as a fence, place few guards inside the fenced region such that wherever an intruder cuts through the fence, the closest guard is at most a distance one away. Restricting the separating objects to be lines, we investigate combinatorial aspects which arise when we use them to pairwise separate a set of points in the plane; hereafter we generalize the notion of separability to arbitrary sets and present several enumeration results. Lastly, we investigate a packing problem with a non-convex shape in ℝ3. We show that ℝ3 can be packed at a density of 0.222 with tori of major radius one and minor radius going to zero. Furthermore, we show that the same torus arrangement yields the asymptotically optimal number of pairwise linked tori.

Download

Included in

Mathematics Commons

Share

COinS