Given an $n$-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of $O(n)$ steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns' 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps.

The symmetric difference is a robust operator for measuring the error of approximating one shape by another. Given two convex shapes P and C, we study the problem of minimizing the volume of their symmetric difference under all possible scalings and translations of C. We prove that the problem can be solved by convex programming. We also present a combinatorial algorithm for convex polygons in the plane that runs in O((m+n) log^3(m+n)) expected time, where n and m denote the number of vertices of P and C, respectively.

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 n /log log n ). We give an O ( n log log n )-space adaptive data structure that improves the query time to O (log log n + log k /log log n ), 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 et al., 2011]. —We give an O ( n log log n )-space data structure for approximate 2-D orthogonal range counting that can compute a (1 + δ)-factor approximation to the count in O (log log n ) time for any fixed constant δ > 0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem. —Last, we consider the 1-D range selection problem, where a query in an array involves finding the k th least element in a given subarray. This problem is closely related to 2-D 3-sided orthogonal range counting. Recently, Jørgensen and Larsen [2011] presented a linear-space adaptive data structure with query time O (log log n + log k /log log n ). We give a new linear-space structure that improves the query time to O (1 + log k /log log n ), exactly matching the lower bound proved by Jørgensen and Larsen.

In many scientific fields, it is common to encounter raster data sets consisting of categorical data, such as soil type or land usage of a terrain. A problem that arises in the presence of such data is the following: given a raster G of n cells storing categorical data, compute for every cell c in G the number of different categories appearing within a window centered at c. The window can either be a (2r+1)x(2r+1) square or a disk of radius r for a positive integer parameter r. We call this the categorical richness problem, and we present two algorithms for it: one for square windows that runs in O(n) time and one for circular windows that runs in O((1+K/r)n) time, where K is the number of distinct categories in G. The algorithms are not only efficient in theory, but also in practice: our experiments show that our algorithms can handle raster data of hundreds of millions of cells.

In the concurrent range reporting (CRR) problem, the input is L disjoint sets S1, …, SL of points in ℝ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 set Q ⊆ {1, …, L}, we can efficiently report all the points in Si ∩ r for each i ∊ Q. The problem was studied as early as 1986 by Chazelle and Guibas [9] and has recently re-emerged when studying higher-dimensional complexity of orthogonal range reporting [2, 3]. 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 Ω(|Q| log(L/|Q|) + logN + 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)+logN + K) time, improving the best previously known query times of O(|Q|log(N/|Q|) + K) and O(2LL + log N + K). Finally, we give an optimal data structure for three-sided ranges for the case L = O(logN).

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(n2) 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(n4) steps.

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(logw n). We give an O(n log log n)-space adaptive data structure that improves the query time to O (log log n + logw 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 log log n)-space data structure for approximate 2-D orthogonal range counting that can compute a (1 + δ)-factor approximation to the count in O (log log 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 (log log n + logw k). We give a new linear-space structure that improves the query time to O(1 + logw k), exactly matching the lower bound proved by Jørgensen and Larsen.

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 O(sqrt(n) loglog n) query time. 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. 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) by sqrt(n) matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for orthogonal range mode in higher dimensions (queries in near O(n^(1-1/2d)) time) and for halfspace range mode in higher dimensions (queries in O(n^(1-1/d^2)) time).