Design, analysis and implemenation of algorithms and
data structures;
Computational Geometry, Graph Theory.
I am a Ph.D. Candidate in the UCI Center for Algorithms and Theory of Computation
I am co-advised by David Eppstein and Michael T. Goodrich
| Email: | jsimons at uci dot edu |
| Office: | DBH 4219 |
Bibliography on DBLP. Preprints on arXiv.
We show that a transitively reduced digraph has a confluent upward drawing if and only if its reachability relation has order dimension at most two. In this case, we construct a confluent upward drawing with $O(n^2)$ features, in an $O(n) \times O(n)$ grid in $O(n^2)$ time. For the digraphs representing series-parallel partial orders we show how to construct a drawing with $O(n)$ features in an $O(n) \times O(n)$ grid in $O(n)$ time from a series-parallel decomposition of the partial order. Our drawings are optimal in the number of confluent junctions they use.
| Joint work with David Eppstein. |
| Slides presented at Graph Drawing 2011. |
| Preprint on arXiv. |
We describe fully retroactive dynamic data structures for approximate range reporting and approximate nearest neighbor reporting. We show how to maintain, for any positive constant $d$, a set of $n$ points in $\mathbb{R}^d$ indexed by time such that we can perform insertions or deletions at any point in the timeline in $O(\log n)$ amortized time. We support, for any small constant $\epsilon>0$, $(1+\epsilon)$-approximate range reporting queries at any point in the timeline in $O(\log n + k)$ time, where $k$ is the output size. We also show how to answer $(1+\epsilon)$-approximate nearest neighbor queries for any point in the past or present in $O(\log n)$ time.
| Joint work with Michael T. Goodrich. |
| Slides presented at ISAAC 2011. |
| Preprint on arXiv. |
We show that several problems of compacting orthogonal graph drawings to use the minimum number of rows, area, length of longest edge or total edge length cannot be approximated to within better than a polynomial factor in polynomial time unless it's the case that $\mathsf{P} = \mathsf{NP}$. We also provide a fixed-parameter-tractable algorithm for testing whether a drawing can be compacted to a small number of rows.
| Joint work with Michael Bannister. and David Eppstein. |
| To appear in the special issue of JGAA for . |
| Preprint on arXiv. |
We give a new efficient data-oblivious PRAM simulation and several new data-oblivious graph-drawing algorithms with application to privacy-preserving graph-drawing in a cloud computing context.
| Joint work with Michael T. Goodrich . |
| Poster presented at GD 2012 . |