Dijkstra's algorithm is the standard method for computing shortest paths on arbitrary graphs. However, it is slow for large graphs, taking at least linear time. It has been long known that for real world road networks, creating a hierarchy of well-chosen shortcuts allows fast distance and path computation, with exact distance queries seemingly being answered in logarithmic time. However, these methods were but heuristics until the work of Abraham et al. [JACM 2016], where they defined a graph parameter called highway dimension which is constant for real-world road networks, and showed that in graphs of constant highway dimension, a shortcut hierarchy exists that guarantees shortest distance computation takes O(log(U+V)) time and O(V log(U+V)) space, where U is the ratio of the smallest to largest edge, and V is the number of vertices. The problem is that they were unable to efficiently compute the hierarchy of shortcuts. Here we present a simple and efficient algorithm to compute the needed hierarchy of shortcuts in time and space O(V log(U+V)), as well as supporting updates in time O( log(U+V)).

It is shown how to enhance any data structure in the pointer model to make it confluently persistent, with efficient query and update times and limited space overhead. Updates are performed in O(logn) amortized time, and following a pointer takes O(logc logn) time where c is the in-degree of a node in the data structure. In particular, this proves that confluent persistence can be achieved at a logarithmic cost in the bounded in-degree model used widely in previous work. This is a O(n/logn)-factor improvement over the previous known transform to make a data structure confluently persistent.

We prove that for every centrally symmetric convex polygon Q, there exists a constant alpha such that any alpha*k-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Toth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery lifetime.

In this paper we propose novel algorithms for reconfiguring cube-style modular robots that are composed of n identical atoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach/detach to faces of neighboring atoms. For universal reconfiguration, it is necessary for atoms to be arranged in 2x2x2 modules. We respect certain physical constraints: each module reaches at most unit velocity and (via expansion) can displace at most one other module. We only require one of the modules to be able to store a map of the target configuration.

Reconfiguration via our algorithms involves a total of O(n^2) such atom operations, but is performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n^2) parallel steps or do not respect the constraints mentioned above. In fact, in the setting considered, our algorithms are worst-case optimal. A further advantage by our algorithmsis that reconfiguration can take place within the union of the source and target configurations.

Let C be a compact and convex set in the plane that contains the origin in its interior, and let S be a finite set of points in the plane. The Delaunay graph DG_C(S) of S is defined to be the dual of the Voronoi diagram of S with respect to the convex distance function defined by C. We prove that DG_C(S) is a t-spanner for S, for some constant t that depends only on the shape of the set C. Thus, for any two points p and q in S, the graph DG_C(S) contains a path between p and q whose Euclidean length is at most t times the Euclidean distance between p and q.

We consider a model of reconfigurable robot, introduced and prototyped by the robotics community. The robot consists of independently manipulable unit-square atoms that can extend/contract arms on each side and attach/detach from neighbors. The optimal worst-case number of sequential moves required to transform one connected configuration to another was shown to be Theta(n) at ISAAC 2007. However, in principle, atoms can all move simultaneously. We develop a parallel algorithm for reconfiguration that runs in only O(log n) parallel steps, although the total number of operations increases slightly to Theta(n log n). The result is the first (theoretically) almost-instantaneous universally reconfigurable robot built from simple units.

We study several coloring problems for geometric range-spaces. In addition to their theoretical interest, some of these problems arise in sensor networks. Given a set of points in R^2 or R^3, we want to color them such that every region of a certain family (e.g., every disk containing at least a certain number of points) contains points of many different colors. In this paper, we think of the number of colors and the number of points as functions of k. Obviously, for a fixed k using k colors, it is not always possible to ensure that every region containing k points has all colors present. Thus, we introduce two types of relaxations: either we allow the number of colors to increase to c(k), or we require that the number of points in each region increases to p(k).

Symmetrically, given a finite set of regions in R^2 or R^3, we want to color them such that every point covered by a sufficiently large number of regions is contained in regions of k different colors. This requires the number of covering regions or the number of allowed colors to be greater than k.

The goal of this paper is to bound these two functions for several types of region families, such as halfplanes, halfspaces, disks and pseudo-disks. We improve and generalize previous results of Pach, Tardos and Toth on decompositions of space coverings.

A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that differs from the optimal one by only lower order terms in the linear comparison tree model.

In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2 x 2 x 2 meta-modules. The reconfiguration involves a total of O(n) atom operations (expand, contract, attach, detach) and is performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which require O(n^2) parallel steps. Our algorithm is in place; that is, the reconfiguration takes place within the union of the bounding boxes of the source and target robots. We show that the algorithm can also be implemented in a synchronous, distributed fashion.

We investigate the global scheduling of sporadic, implicit deadline, real-time task systems on identical multiprocessor platforms. We provide a task model which integrates work-limited job parallelism. For work-limited parallelism, we prove that the time-complexity of deciding if a task set is feasible is linear relatively to the number of (sporadic) tasks for a fixed number of processors. Based on this proof, we propose an optimal scheduling algorithm. Moreover, we provide an exact feasibility utilization bound.

We analyze a new popular video-game called Lumines, which was developed by Sony for the PSP platform. It involves a sequence of bichromatic 2x2 blocks that fall in a grid and must be shifted or rotated by the player before they land. Patterns of monochromatic 2x2 blocks in the terrain are regularly deleted. The primary goal is to contain the terrain within a fixed height and, if possible, clear the grid. We deal with questions such as the following: Can the game be played indefinitely? Can all terrains be eliminated? We examine how answers to these questions depend on the size of the grid and the rate at which blocks are deleted.

Rushhour is a sliding block game where blocks represent cars stuck in a traffic jam on a 6x6 board. The goal of the game is to allow one of the cars (the target car) to exit this traffic jam by moving the other cars out of its way. In this paper, we study the problem of finding difficult initial configurations for this game. An initial configuration is difficult if the number of car moves necessary to exit the target car is high. To solve the problem, we model the game in propositional logic and we apply symbolic model-checking techniques to study the huge graph of configurations that underlies the game. On the positive side, we show that this huge graph (containing 3.6x10^10 vertices) can be completely analyzed using symbolic model-checking techniques with reasonable computing resources. We have classified every possible initial configuration of the game according to the length of its shortest solution. On the negative side, we prove a general theorem that shows some limits of symbolic model-checking methods for board games. This result explains why some natural modeling of board games leads to the explosion of the size of symbolic data-structures.