William Evans

Associate Professor

Research Classification

Algorithms
Theoretical Computer Science
Computer Sciences and Mathematical Tools

Research Interests

theoretical computer science
computational geometry
graph drawing
program compression

Relevant Degree Programs

 

Recruitment

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 "Requirements" 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 peek 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.

 

Master's students
Doctoral students
2019
2020

Graduate Student Supervision

Doctoral Student Supervision (Jan 2008 - May 2019)
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 (2010 - 2018)
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.