Education

2016

University of Waterloo
Master of Mathematics in Computer Science
GPA: 96.25%
Supervisor: Timothy M. Chan
  •  
    NSERC Canada Graduate Scholarship - Master's
    2016, 2015
  •  
    Ontario Graduate Scholarship
    2015, 2014
  •  
    President's Graduate Scholarship
    2016, 2015, 2014

2014

Carleton University
Bachelor of Computer Science
GPA: 11.64/12
Supervisor: Michiel Smid
  •  
    Senate Medal for Outstanding Academic Achievement
    2014
  •  
    NSERC Undergraduate Student Research Award
    2013, 2012, 2011
  •  
    Tracey and Siva Ananmalay Scholarship in Computer Science
    2013
  •  
    Michael Oliver Scholarship
    2012
  •  
    Gerhard Herzberg Scholarship
    2011

Publications

Theses

2016

  • Three approaches to building time-windowed geometric data structures


    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 time-windowed decision problems. We present algorithms to preprocess for the time-windowed closest pair decision problem in $O(n)$ expected time, for the time-windowed 2D diameter decision problem in $O(n \log n)$ time, the time-windowed 2D convex hull area decision problem in $O(n \alpha(n) \log n)$ time (where $\alpha$ is the inverse Ackermann function), and the time-windowed 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 time-windowed 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.
    Simon Pratt.
    Master’s thesis, University of Waterloo, 2016.
    @mastersthesis{pratt2016three,
      author={Pratt, Simon},
      title={Three approaches to building time-windowed geometric data structures},
      type={Master's thesis},
      school={University of Waterloo},
      year={2016}
    }
    

Conference papers

Conference papers that I presented are marked with (presented).(Icon by Double-J Design, used under a Creative Commons Attribution license)

2016

  • Time-space trade-offs for triangulating a simple polygon


    Abstract: An $s$-workspace algorithm is an algorithm that has read-only access to the values of the input, write-only 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$.
    Boris Aronov, Matias Korman, Simon Pratt, André van Renssen, and Marcel Roeloffzen.
    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={Time-Space Trade-offs for Triangulating a Simple Polygon},
      booktitle={Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)},
      year={2016},
      volume={53},
      pages={30--1},
      doi={10.4230/LIPIcs.SWAT.2016.30}
    }
    
  • Two approaches to building time-windowed geometric data structures


    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 time-windowed 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 time-windowed 2D diameter decision problem in $O(n \log n)$ time and the time-windowed 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 time-windowed 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 time-windowed 3D diameter decision and 2D orthogonal segment intersection detection problems.
    Timothy M. Chan and Simon Pratt.
    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 Time-Windowed Geometric Data Structures},
      booktitle={Proceedings of the 32nd International Symposium on Computational Geometry (SoCG)},
      year={2016},
      volume={51},
      pages={28--1},
      doi={10.4230/LIPIcs.SoCG.2016.28}
    }
    

2015

  • Time-windowed closest pair


    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 quadtree-based approach in the word-RAM model.
    Timothy M. Chan and Simon Pratt.
    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={Time-Windowed Closest Pair},
      booktitle={Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG)},
      year={2015},
      pages={141--144}
    }
    

2014

  • The convex hull of points on a sphere is a spanner


    Abstract: Let $S$ be a finite set of points on the unit-sphere $\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.
    Prosenjit Bose, Simon Pratt, and Michiel Smid.
    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={244--250}
    }
    

Generated by Publy 1.1.  Last modified on 18 August 2016.