Bryan T. Wilkinson

PhD candidate

Revisiting visibility in the plane

Bryan T. Wilkinson

View Abstract

We consider two closely related problems: computing the region visible from a point amid simple polygonal obstacles and computing the lower envelope of a set of disjoint segments. Visibility problems such as these were proposed and promptly solved in the late ’80s and early ’90s before the widespread popularity of the word RAM model. All previously published algorithms thus run in Omega(n log n) time, although they can be sped up in the word RAM model to some extent by substituting appropriate word RAM data structures and algorithms. Our main result is a deterministic linear-time algorithm for the case in which endpoints are presorted. Using the fastest known integer sorting algorithm of Han and Thorup (FOCS 2002), we thus obtain an algorithm for the general case that runs in O(n sqrt{loglog n}) time. We expect our algorithm for the presorted case to be practically efficient. Our algorithm actually solves the more general problem of computing the lower envelope of a set of non-intersecting partial functions defined over intervals.

We obtain our results via a novel approach that considers a partial lower envelope problem in which we need only find the lowest partial function at q <= 2n x-coordinates. We combine this algorithm with another that exploits the bounded precision of x-coordinates of endpoints and otherwise performs only comparisons to determine the vertical ordering of partial functions. In addition to our word RAM result, we obtain a better understanding of the inherent complexity of our visibility problems, resulting in a pointer machine algorithm that runs in O(n α(n)) time as long as endpoints are appropriately presorted.

Submitted.

Amortized bounds for dynamic orthogonal range reporting

Bryan T. Wilkinson

View Abstract

We consider the fundamental problem of 2-D dynamic orthogonal range reporting for 2- and 3-sided queries in the standard word RAM model. While many previous dynamic data structures use O(log n / loglog n) update time, we achieve faster O((log n)^{1/2+ε}) and O((log n)^{2/3+ε}) update times for 2- and 3-sided queries, respectively. Our data structures have optimal O(log n / loglog n) query time. Only Mortensen (SICOMP 2006) had previously lowered the update time convincingly below O(log n), with 3- and 4-sided data structures supporting updates in O((log n)^{5/6+ε}) and O((log n)^{7/8+ε}) time, respectively. In practice, fast updates are often as important as fast queries, so we make a step forward for an important problem that has not seen any progress in recent years.

We also obtain new results for the special case of 3-sided insertion-only emptiness, showing that the difference in complexity between fully dynamic and partially dynamic 2-D orthogonal range reporting can be significant (i.e., Omega(polylog n) factor differences). In particular, we achieve O((log n loglog n)^{2/3}) update time and O((log n loglog n)^{1/3}) query time. At the other end of our update/query trade-off curve, we achieve O(log n / loglog n) update time and O(loglog n) query time. In contrast, in the pointer machine model, there are only O(loglog n) factor differences between the complexities of fully dynamic and partially dynamic 2-D orthogonal range reporting.

ESA’14: 22nd European Symposium on Algorithms

Property testing on linked lists

Peyman Afshani, Kevin Matulef, Bryan T. Wilkinson

View Abstract

We define a new property testing model for algorithms that do not have arbitrary query access to the input, but must instead traverse it in a manner that respects the underlying data structure in which it is stored. In particular, we consider the case when the underlying data structure is a linked list, and the testing algorithm is allowed to either sample randomly from the list, or walk to nodes that are adjacent to those already visited. We study the well-known monotonicity testing problem in this model, and show that Theta(n^{1/3}) queries are both necessary and sufficient to distinguish whether a list is sorted (monotone increasing) versus a constant distance from sorted. Our bound is strictly greater than the Theta(log n) queries required in the standard testing model, that allows element access indexed by rank, and strictly less than the Theta(sqrt{n}) queries required by a weak model that only allows random sampling.

ECCC: Electronic Colloquium on Computational Complexity

Concurrent range reporting in two-dimensional space

Peyman Afshani, Cheng Sheng, Yufei Tao, Bryan T. Wilkinson

View Abstract

In the concurrent range reporting (CRR) problem, the input is L disjoint sets S_1, …, S_L of points in R^d with a total of N points. The goal is to preprocess the sets into a structure such that, given a query range r and an arbitrary subset Q of {1, …, L}, we can efficiently report all the points in the intersection of S_i and r for each i in Q. The problem was studied as early as 1986 by Chazelle and Guibas and has recently re-emerged when studying higher-dimensional complexity of orthogonal range reporting.

We focus on the one- and two-dimensional cases of the problem. We prove that in the pointer-machine model (as well as comparison models such as the real RAM model), answering queries requires Omega(|Q| log (L/|Q|) + log N + K) time in the worst case, where K is the number of output points. In one dimension, we achieve this query time with a linear-space dynamic data structure that requires optimal O(log N) time to update. We also achieve this query time in the static case for dominance and halfspace queries in the plane. For three-sided ranges, we get close to within an inverse Ackermann (α(.)) factor: we answer queries in O(|Q| log (L/|Q|) α(L) + log N + K) time, improving the best previously known query times of O(|Q| log (N/|Q|) + K) and O(2^L L + log N + K). Finally, we give an optimal data structure for three-sided ranges for the case L = O(log N).

SODA’14: 25th Symposium on Discrete Algorithms

Adaptive and approximate orthogonal range counting

Timothy M. Chan, Bryan T. Wilkinson

View Abstract

We present three new results on one of the most basic problems in geometric data structures, 2-D orthogonal range counting. All the results are in the w-bit word RAM model.

  • It is well known that there are linear-space data structures for 2-D orthogonal range counting with worst-case optimal query time O(log_w n). We give an O(n loglog n)-space adaptive data structure that improves the query time to O(loglog n + log_w k), where k is the output count. When k = O(1), our bounds match the state of the art for the 2-D orthogonal range emptiness problem [Chan, Larsen, and Pătraşcu, SoCG 2011].
  • We give an O(n loglog n)-space data structure for approximate 2-D orthogonal range counting that can compute a (1+δ)-factor approximation to the count in O(loglog n) time for any fixed constant δ > 0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem.
  • Lastly, we consider the 1-D range selection problem, where a query in an array involves finding the kth least element in a given subarray. This problem is closely related to 2-D 3-sided orthogonal range counting. Recently, Jørgensen and Larsen [SODA 2011] presented a linear-space adaptive data structure with query time O(loglog n + log_w k). We give a new linear-space structure that improves the query time to O(1 + log_w k), exactly matching the lower bound proved by Jørgensen and Larsen.

SODA’13: 24th Symposium on Discrete Algorithms

Morphing planar graph drawings with a polynomial number of steps

Soroush Alamdari, Patrizio Angelini, Timothy M. Chan, Giuseppe Di Battista, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, Bryan T. Wilkinson

View Abstract

In 1944, Cairns proved the following theorem: given any two straight-line planar drawings of a triangulation with the same outer face, there exists a morph (i.e., a continuous transformation) between the two drawings so that the drawing remains straight-line planar at all times. Cairns’s original proof required exponentially many morphing steps. We prove that there is a morph that consists of O(n^2) steps, where each step is a linear morph that moves each vertex at constant speed along a straight line. Using a known result on compatible triangulations this implies that for a general planar graph G and any two straight-line planar drawings of G with the same embedding, there is a morph between the two drawings that preserves straight-line planarity and consists of O(n^4) steps.

SODA’13: 24th Symposium on Discrete Algorithms

Adaptive range counting and other frequency-based range query problems

Bryan T. Wilkinson

View Abstract

We consider variations of range searching in which, given a query range, our goal is to compute some function based on frequencies of points that lie in the range. The most basic such computation involves counting the number of points in a query range. Data structures that compute this function solve the well-studied range counting problem. We consider adaptive and approximate data structures for the 2-D orthogonal range counting problem under the w-bit word RAM model. The query time of an adaptive range counting data structure is sensitive to k, the number of points being counted. We give an adaptive data structure that requires O(n loglog n) space and O(loglog n + log_w k) query time. Non-adaptive data structures on the other hand require Omega(log_w n) query time (Pătraşcu, 2007). Our specific bounds are interesting for two reasons. First, when k = O(1), our bounds match the state of the art for the 2-D orthogonal range emptiness problem (Chan et al., 2011). Second, when k = Theta(n), our data structure is tight to the aforementioned Omega(log_w n) query time lower bound.

We also give approximate data structures for 2-D orthogonal range counting whose bounds match the state of the art for the 2-D orthogonal range emptiness problem. Our first data structure requires O(n loglog n) space and O(loglog n) query time. Our second data structure requires O(n) space and O(log^ε n) query time for any fixed constant ε > 0. These data structures compute an approximation k’ such that (1-δ)k ≤ k’ ≤ (1+δ)k for any fixed constant δ > 0.

The range selection query problem in an array involves finding the kth lowest element in a given subarray. Range selection in an array is very closely related to 3-sided 2-D orthogonal range counting. An extension of our technique for 3-sided 2-D range counting yields an efficient solution to adaptive range selection in an array. In particular, we present an adaptive data structure that requires O(n) space and O(log_w k) query time, exactly matching a recent lower bound (Jørgensen and Larsen, 2011).

We next consider a variety of frequency-based range query problems in arrays. We give efficient data structures for the range mode and least frequent element query problems and also exhibit the hardness of these problems by reducing Boolean matrix multiplication to the construction and use of a range mode or least frequent element data structure. We also give data structures for the range α-majority and α-minority query problems. An α-majority is an element whose frequency in a subarray is greater than an α fraction of the size of the subarray; any other element is an α-minority. Surprisingly, geometric insights prove to be useful even in the design of our 1-D range α-majority and α-minority data structures.

Master’s thesis (University of Waterloo)

Linear-space data structures for range minority query in arrays

Timothy M. Chan, Stephane Durocher, Matthew Skala, Bryan T. Wilkinson

View Abstract

We consider range queries in arrays that search for low-frequency elements: least frequent elements and α-minorities. An α-minority of a query range has multiplicity no greater than an α fraction of the elements in the range. Our data structure for the least frequent element range query problem requires O(n) space, O(n^{3/2}) preprocessing time, and O(sqrt{n}) query time. A reduction from boolean matrix multiplication to this problem shows the hardness of simultaneous improvements in both preprocessing time and query time. Our data structure for the α-minority range query problem requires O(n) space, supports queries in O(1/α) time, and allows α to be specified at query time.

SWAT’12: 13th Scandinavian Workshop on Algorithm Theory
Algorithmica

Linear-space data structures for range mode query in arrays

Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, Bryan T. Wilkinson

View Abstract

A mode of a multiset S is an element a in S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1:n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i, j) for which a mode of A[i:j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (ISAAC 2003), requires Theta(sqrt{n} loglog n) query time in the worst case. We improve their result and present an O(n)-space data structure that supports range mode queries in O(sqrt{n/log n}) worst-case time. In the external memory model, we give a linear-space data structure that requires O(sqrt{n/B}) I/Os per query, where B denotes the block size. Furthermore, we present strong evidence that a query time significantly below sqrt(n) cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two sqrt(n) x sqrt(n) matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for the dynamic problem (queries and updates in near O(n^{3/4}) time), for orthogonal range mode in d dimensions (queries in near O(n^{1-1/2d}) time) and for half-space range mode in d dimensions (queries in O(n^{1-1/d^2}) time). Finally, we complement our dynamic data structure with a reduction from the multiphase problem, again supporting that we cannot hope for much more efficient data structures.

STACS’12: 29th Symposium on Theoretical Aspects of Computer Science
ToCS: Theory of Computing Systems (STACS’12 special issue)

Bichromatic line segment intersection counting in O(n sqrt{log n}) time

Timothy M. Chan, Bryan T. Wilkinson

View Abstract

We give an algorithm for bichromatic line segment intersection counting that runs in O(n sqrt{log n}) time under the word RAM model via a reduction to dynamic predecessor search, offline point location, and offline dynamic ranking. This algorithm is the first to solve bichromatic line segment intersection counting in o(n log n) time.

CCCG’11: 23rd Canadian Conference on Computational Geometry