Education
2016
University of Waterloo
Master of Mathematics in Computer Science
GPA: 96.25%
Supervisor: Timothy M. Chan

NSERC Canada Graduate Scholarship  Master's2016, 2015

Ontario Graduate Scholarship2015, 2014

President's Graduate Scholarship2016, 2015, 2014
2014
Carleton University
Bachelor of Computer Science
GPA: 11.64/12
Supervisor: Michiel Smid

Senate Medal for Outstanding Academic Achievement2014

NSERC Undergraduate Student Research Award2013, 2012, 2011

Tracey and Siva Ananmalay Scholarship in Computer Science2013

Michael Oliver Scholarship2012

Gerhard Herzberg Scholarship2011
Publications
Theses
2016

Three approaches to building timewindowed geometric data structures
Simon Pratt.Abstract: Given a set of geometric objects (points or line segments) each associated with a time value, we wish to determine whether a given property is true for a subset of those objects whose time values fall within a query time window. We call such problems timewindowed decision problems. We present algorithms to preprocess for the timewindowed closest pair decision problem in $O(n)$ expected time, for the timewindowed 2D diameter decision problem in $O(n \log n)$ time, the timewindowed 2D convex hull area decision problem in $O(n \alpha(n) \log n)$ time (where $\alpha$ is the inverse Ackermann function), and the timewindowed 3D diameter decision and orthogonal segment intersection detection problems in $O(n \mathop{polylog} n)$ time. Our first approach is to reduce the closest pair decision problem to 2D dominance range emptiness using grids to compute candidate satisfying pairs. We extend this approach to find the closest pair of points by reducing the problem to 2D dominance range minimum, which we further reduce to 2D point location. Our second approach is to reduce timewindowed decision problems to a generalized range successor problem, which we solve using a novel way to search range trees. Our third approach is to use dynamic data structures directly, taking advantage of a new observation that the total number of combinatorial changes to a planar convex hull is near linear for any FIFO update sequence, in which deletions occur in the same order as insertions.
Master’s thesis, University of Waterloo, 2016.
@mastersthesis{pratt2016three, author={Pratt, Simon}, title={Three approaches to building timewindowed geometric data structures}, type={Master's thesis}, school={University of Waterloo}, year={2016} }
Conference papers
Conference papers that I presented are marked with .(Icon by DoubleJ Design, used under a Creative Commons Attribution license)
2016

Timespace tradeoffs for triangulating a simple polygon
Boris Aronov, Matias Korman, Simon Pratt, André van Renssen, and Marcel Roeloffzen.Abstract: An $s$workspace algorithm is an algorithm that has readonly access to the values of the input, writeonly access to the output, and only uses $O(s)$ additional words of space. We give a randomized $s$workspace algorithm for triangulating a simple polygon $P$ of $n$ vertices, for any $s$ up to $n$. The algorithm runs in $O(n^2/s+n(\log s)\log^5(n/s))$ expected time using $O(s)$ variables, for any $s$ up to $n$. In particular, the algorithm runs in $O(n^2/s)$ expected time for most values of $s$.
In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 53, pages 30–1, 2016.
@inproceedings{aronov2016time, author={Aronov, Boris and Korman, Matias and Pratt, Simon and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={TimeSpace Tradeoffs for Triangulating a Simple Polygon}, booktitle={Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)}, year={2016}, volume={53}, pages={301}, doi={10.4230/LIPIcs.SWAT.2016.30} }

Two approaches to building timewindowed geometric data structures
Timothy M. Chan and Simon Pratt.Abstract: Given a set of geometric objects each associated with a time value, we wish to determine whether a given property is true for a subset of those objects whose time values fall within a query time window. We call such problems timewindowed decision problems, and they have been the subject of much recent attention, for instance studied by Bokal, Cabello, and Eppstein [SoCG 2015]. In this paper, we present new approaches to this class of problems that are conceptually simpler than Bokal et al.’s, and also lead to faster algorithms. For instance, we present algorithms for preprocessing for the timewindowed 2D diameter decision problem in $O(n \log n)$ time and the timewindowed 2D convex hull area decision problem in $O(n \alpha(n) \log n)$ time (where $\alpha$ is the inverse Ackermann function), improving Bokal et al.’s $O(n \log^2 n)$ and $O(n \log n \log\log n)$ solutions respectively. Our first approach is to reduce timewindowed decision problems to a generalized range successor problem, which we solve using a novel way to search range trees. Our other approach is to use dynamic data structures directly, taking advantage of a new observation that the total number of combinatorial changes to a planar convex hull is near linear for any FIFO update sequence, in which deletions occur in the same order as insertions. We also apply these approaches to obtain the first $O(n \mathop{polylog} n)$ algorithms for the timewindowed 3D diameter decision and 2D orthogonal segment intersection detection problems.
In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG), volume 51, pages 28–1, 2016.
@inproceedings{chan2016two, author={Chan, Timothy M. and Pratt, Simon}, title={Two Approaches to Building TimeWindowed Geometric Data Structures}, booktitle={Proceedings of the 32nd International Symposium on Computational Geometry (SoCG)}, year={2016}, volume={51}, pages={281}, doi={10.4230/LIPIcs.SoCG.2016.28} }
2015

Timewindowed closest pair
Timothy M. Chan and Simon Pratt.Abstract: Given a set of points in any constant dimension, each of which is associated with a time during which that point is active, we design a data structure with $O(n \log n)$ space that can find the closest pair of active points within a query interval of time in $O (\log \log n)$ time using a quadtreebased approach in the wordRAM model.
In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG), pages 141–144, 2015.
@inproceedings{chan2015time, author={Chan, Timothy M. and Pratt, Simon}, title={TimeWindowed Closest Pair}, booktitle={Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG)}, year={2015}, pages={141144} }
2014

The convex hull of points on a sphere is a spanner
Prosenjit Bose, Simon Pratt, and Michiel Smid.Abstract: Let $S$ be a finite set of points on the unitsphere $\mathbb{S}^2$. In 1987, Raghavan suggested that the convex hull of $S$ is a Euclidean $t$spanner, for some constant $t$. We prove that this is the case for $t= 3\pi (\pi/2+ 1)/2$. Our proof consists of generalizing the proof of Dobkin et al. from the Euclidean Delaunay triangulation to the spherical Delaunay triangulation.
In Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG), pages 244–250, 2014.
@inproceedings{bose2014convex, author={Bose, Prosenjit and Pratt, Simon and Smid, Michiel}, title={The Convex Hull of Points on a Sphere is a Spanner}, booktitle={Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG)}, year={2014}, pages={244250} }
Generated by Publy 1.1. Last modified on 18 August 2016.