William Evans

In this thesis we consider the problem faced by an agent who is tasked with inspecting certain objects within the plane. In particular, given some starting position notinterior to a convex polygon the agent must traverse through the plane to fully seeall edges of the polygon. However traversal is expensive for the agent and so theagent would like to determine the shortest path it can take such that all edges ofthe polygon will be seen from the path. For all polygons and feasible starting positions we present an efficient algorithm for determining what the shortest path is bycharacterizing properties that any such path must exhibit.Next we consider how the agent should accomplish this task when it is onlyaware that the polygon it is to inspect is convex, but not its shape (i.e. location ofedges.) In such a scenario the agent must search for the edges by traversing throughthe plane. Yet if such searching is not done in an efficient manner, the distancetraversed may be unacceptably large with respect to the length of the optimal path.We discuss several strategies that the agent can employ that will ensure that thedistance it traverses to see all edges is at most a constant times the length of theoptimal path.

View record

A t-spanner is a graph in which the shortest path between two vertices never exceeds t times the distance between the two nodes – a t-approximation of the complete graph. A geometric graph is one in which its vertices are points with defined coordinates and the edges correspond to line segments between them with a distance function, such as Euclidean distance. Geometric spanners are used to design networks of reduced complexity, optimizing metrics such as the planarity or degree of the graph.One famous algorithm used to generate spanners is path-greedy, which scans pairs of points in non-decreasing order of distance and adds the edge between them unless the current set of added edges already connects them with a path that t-approximates the edge length. Graphs from this algorithm are called path-greedy spanners. This work analyzes properties of path-greedy geometric spanners under different conditions.Specifically, we answer an open problem regarding the planarity and degree of path-greedy 5.19-spanners in convex point sets, and explore how the algorithm behaves under random tiebreaks for grid point sets. Lastly, we show a simple and efficient way to reduce the degree of a plane spanner by adding extra points.

View record

Let e1, e2, . . . , en be a set of entities moving with bounded speed in d-dimensional space. At each time step, we can choose one entity to query to obtain its actual location. Our goal is to establish via these queries that many of the entities could not be at a fixed point called a beacon. By failing to query an entity, the set of its potential locations, called its uncertainty region, grows over time. We want to query to keep the number of uncertainty regions that do not overlap the beacon (i.e., the number of entities away from the beacon) as large as possible. Of course, if many entities are near the beacon, we cannot avoid high overlap, but neither can any query schedule. We describe query schedules that establish that the number of entities away from the beacon is a constant fraction of the maximum number that can be shown to be away from the beacon inthe case where each entity is static that is, every query reveals that the entity has not moved. In the general setting we show additive upper and lower bounds on what can be attained by a query schedule.

View record

The problem of finding a shortest Euclidean path in an arrangement of lines between two points in the arrangement has been extensively studied; however, the best known exact solution takes quadratic time, and it’s not known if a subquadratic time algorithm exists.While I did not succeed in improving these bounds, I examined instead the problem of efficiently finding the approximate shortest path where the runtime depends on the bound of the relative error in the path length. I present an algorithm for computing this approximate shortest path. The algorithm uses the geometric structure of the arrangement; I show that certain lines are never used by the shortest path, while other lines could be ignored without making the path much longer.My work includes a number of lemmas that provide simple proofs for related problems (such as shortest path in two intersecting pencils of lines), and could have applications in future work on this problem.

View record

Suppose we want to compute some function (such as convex hull or k-th smallest element), but the input values are imprecise. Can we compute the answer? Perhaps we need some of the input values to be more precise. What is the smallest additional input precision we need for each input to compute the function? We explore a model in which a query to an input allows us to uncover one more "unit" of its precision, at unit cost. Unfortunately, we cannot predict the results of a query in advance. This motivates us to study online algorithms that attempt to minimize the number of queries to compute the function. We compare the cost of online algorithms against the minimum query cost to compute the function. We obtain lower bounds on the ratio of these costs for a variety of simple functions, and create algorithms with matching upper bounds. We also consider a kinetic model in which the results of a query become more imprecise over time (i.e., the inputs move) and our goal is to compute the function of the inputs at some fixed time.

View record

A terrain is an x-monotone polygonal line in the xy-plane. Two vertices of a terrain are mutually visible if and only if they are adjacent or the line segment that connects them lies above the terrain (except at its endpoints). A graph whose vertices represent terrain vertices and whose edges represent mutually visible pairs of terrain vertices is called a terrain visibility graph. Understanding the graph theoretic properties of all terrain visibility graphs may help us understand the combinatorial structure of these geometric objects and help to address problems related to geometric visibility. The properties that are true of all terrain visibility graphs are called necessary properties. The set of properties that, if true, imply that a graph is a terrain visibility graph is called a sufficient set. We would like to find properties that are both necessary and sufficient; that is, we would like to characterize, graph theoretically, terrain visibility graphs.Abello et al. [Discrete and Computational Geometry,14(3):331–358,1995] studied the core induced subgraphs of the visibility graphs of staircase polygons, which are exactly the class of terrain visibility graphs. They showed that the visibility between vertices in such structures implies some ordering requirements on the slopes of the lines that connect pairs of vertices in any realization. They approached the problem of whether certain graph properties are sufficient by creating a slope order on the lines that connect all pairs of polygon vertices (in a possible realization) such that the slope order is consistent with the desired visibility graph. The main contribution of our work is to give a much simpler proof that these properties guarantee such a slope ordering. Our proof consequently gives a faster algorithm for constructing this slope order. Our approach attempts to clarify the implications of the graph theoretic properties on the ordering of the slopes, and may be interpreted as defining properties on an underlying oriented matroid.

View record

Given a polygon P, we considered the problem of finding the shortest total paths for two and three mobile guards to cover P. In our definition of the problem, we do not limit the movements of the guards. The guards are allowed to start their paths at any point on the polygon, cross the interior or intersect each other's paths if necessary. A polygon P is covered by two guards if every point in P is on the line that connects the guards at some point in time. We proved that if the polygon is convex, the optimal sweep limits the paths of the guards to the perimeter of the polygon. In the optimal solution the guards may start their paths at the end-points of the longest edge of P and end their paths at the end-points of the second longest edge in P, visiting the n-2 other edges along the way. Finding such a path takes O(n) time. With three, the guarding problem is defined differently. In the three guard problem a point is covered if it is on the triangle formed by the guards at some point in the sweep. We found that even in convex polygons in some cases crossing the polygon makes the sweep shorter. However, we showed that the optimal sweep is always simple (i.e., the guards paths do not cross one another). By recognizing the conditions where interior paths are beneficial we were able to present an algorithm to find the optimal 3-guard path in O(n⁵) time.

View record