William Evans


Research Classification

Research Interests

theoretical computer science
Computer Sciences and Mathematical Tools
computational geometry
graph drawing
program compression
theoretical computer science

Relevant Degree Programs

Affiliations to Research Centres, Institutes & Clusters



Master's students
Doctoral students

Complete these steps before you reach out to a faculty member!

Check requirements
  • Familiarize yourself with program requirements. You want to learn as much as possible from the information available to you before you reach out to a faculty member. Be sure to visit the graduate degree program listing and program-specific websites.
  • Check whether the program requires you to seek commitment from a supervisor prior to submitting an application. For some programs this is an essential step while others match successful applicants with faculty members within the first year of study. This is either indicated in the program profile under "Admission Information & Requirements" - "Prepare Application" - "Supervision" or on the program website.
Focus your search
  • Identify specific faculty members who are conducting research in your specific area of interest.
  • Establish that your research interests align with the faculty member’s research interests.
    • Read up on the faculty members in the program and the research being conducted in the department.
    • Familiarize yourself with their work, read their recent publications and past theses/dissertations that they supervised. Be certain that their research is indeed what you are hoping to study.
Make a good impression
  • Compose an error-free and grammatically correct email addressed to your specifically targeted faculty member, and remember to use their correct titles.
    • Do not send non-specific, mass emails to everyone in the department hoping for a match.
    • Address the faculty members by name. Your contact should be genuine rather than generic.
  • Include a brief outline of your academic background, why you are interested in working with the faculty member, and what experience you could bring to the department. The supervision enquiry form guides you with targeted questions. Ensure to craft compelling answers to these questions.
  • Highlight your achievements and why you are a top student. Faculty members receive dozens of requests from prospective students and you may have less than 30 seconds to pique someone’s interest.
  • Demonstrate that you are familiar with their research:
    • Convey the specific ways you are a good fit for the program.
    • Convey the specific ways the program/lab/faculty member is a good fit for the research you are interested in/already conducting.
  • Be enthusiastic, but don’t overdo it.
Attend an information session

G+PS regularly provides virtual sessions that focus on admission requirements and procedures and tips how to improve your application.


Graduate Student Supervision

Doctoral Student Supervision

Dissertations completed in 2010 or later are listed below. Please note that there is a 6-12 month delay to add the latest dissertations.

Guarantees concerning geometric objects with imprecise points (2011)

Traditional geometric algorithms are often presented as if input imprecision does not exist, even though it is often unavoidable. We argue that in some cases, it may be desirable for geometric algorithms to treat this imprecision as an explicit component of the input, and to reflect this imprecision in the output. Starting with three problems from computational geometry whose inputs are planar point sets (Voronoi diagrams, convex hulls, and smallest bounding discs), we recast these as problems where each input point's location is imprecise, but known to lie within a particular region of uncertainty. Where algorithms to solve each of the original problems produce a single geometric object as output, the algorithms that we present typically produce either guaranteed or possible output objects. A guaranteed object represents qualities that can be guaranteed for every point set that is consistent with the uncertain regions, and a possible object represents qualities that exist for at least one such point set. By dealing with input imprecision explicitly, these guaranteed and possible objects can represent a more accurate view of what can be reliably inferred from the input data.

View record

Master's Student Supervision

Theses completed in 2010 or later are listed below. Please note that there is a 6-12 month delay to add the latest theses.

On competitive strategies for external exploration of a convex polygon (2021)

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

On path-greedy geometric spanners (2021)

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

Scheduling queries to moving entities to certify many are distant from a region (2020)

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

Shortest paths in line arrangements (2020)

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

Computing Functions of Imprecise Inputs Using Query Models (2012)

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

Optimally sweeping convex polygons with two and three guards (2010)

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


If this is your researcher profile you can log in to the Faculty & Staff portal to update your details and provide recruitment preferences.


Read tips on applying, reference letters, statement of interest, reaching out to prospective supervisors, interviews and more in our Application Guide!