We introduce the problem of draining water (or balls representing water drops) out of a punctured polygon (or a polyhedron) by rotating the shape. For 2D polygons, we obtain combinatorial bounds on the number of holes needed, both for arbitrary polygons and for special classes of polygons. We detail an O(n^2 log n) algorithm that finds the minimum number of holes needed for a given polygon, and argue that the complexity remains polynomial for polyhedra in 3D. We make a start at characterizing the 1-drainable shapes, those that only need one hole.

Given an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a non-crossing matching between point-object pairs. In this paper, we address the algorithmic problem of determining whether a non-crossing matching exists between a given point-object pair. We show that when the objects we match the points to are finite point sets, the problem is NP-complete in general, and polynomial when the objects are on a line or when their number is at most 2. When the objects are line segments, we show that the problem is NP-complete in general, and polynomial when the segments form a convex polygon or are all on a line. Finally, for objects that are straight lines, we show that the problem of finding a min-max non-crossing matching is NP-complete.

We introduce a new geometric spanner whose construction is based on a generalization of the known Stable Roommates problem. The Stable Roommates Spanner combines the most desirable properties of geometric spanners: a natural definition, small degree, linear number of edges, strong (1+ε)-spanner, low weight (O(1) × the weight of the minimum spanning tree) and an efficient construction algorithm. It is an improvement over the well-known Yao graph and Θ-graph and their variants. We show how to construct such a spanner in O(n log¹⁰ n). Finally, we show how to construct a variant of the Stable Roommates Spanner called the Stable Roommates Θ-Spanner in O(n log² n). This variant possesses all the properties of the Stable Roommates Spanner except that it is no longer a strong spanner.

A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a constant factor of optimal. More specifically, an algorithm is presented that preprocesses a connected planar subdivision G of size n and a query distribution D to produce a point location data structure for G. The expected number of point-line comparisons performed by this data structure, when the queries are distributed according to D, is H + O(H^2/3+1) where H=H(G,D) is a lower bound on the expected number of point-line comparisons performed by any linear decision tree for point location in G under the query distribution D. The preprocessing algorithm runs in O(n log n) time and produces a data structure of size O(n). These results are obtained by creating a Steiner triangulation of G that has near-minimum entropy.

In this paper we propose novel algorithms for reconfiguring modular robots that are composed of n atoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or detach from faces of neighboring atoms. For universal reconfiguration, atoms must be arranged in 2󫎾 modules. We respect certain physical constraints: each atom reaches at most constant velocity and can displace at most a constant number of other atoms. We assume that one of the atoms has access to the coordinates of atoms in the target configuration. Our algorithms involve a total of O(n2) atom operations, which are 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 optimal. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configuration space, and only requires local communication.

We prove the following generalised empty pentagon theorem: for every integer >=2, every sufficiently large set of points in the plane contains collinear points or an empty pentagon. As an application, we settle the next open case of the Big Line or Big Clique Conjecture of Kára, Pór, and Wood [Discrete Comput. Geom. 34(3):497--506, 2005].

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 prove that for every centrally symmetric convex polygon Q, there exists a constant ? such that any locally finite ? 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 T髏h. The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.

A highway H is a line in the plane on which one can travel at a greater speed than in the remaining plane. One can choose to enter and exit H at any point. The highway time distance between a pair of points is the minimum time required to move from one point to the other, with optional use of H. The highway hull HH(S,H) of a point set S is the minimal set containing S as well as the shortest paths between all pairs of points in HH(S,H), using the highway time distance. We provide a Theta(n log n) worst-case time algorithm to find the highway hull under the L_1 metric, as well as an O(n log^2 n) time algorithm for the L_2 metric which improves the best known result of O(n^2). We also define and construct the useful region of the plane: the region that a highway must intersect in order that the shortest path between at least one pair of points uses the highway.

We introduce and analyze sigma-local graphs, based on a definition of locality by Erickson. We present two algorithms to construct such graphs, for any real number sigma>1 and any set S of n points. These algorithms run in time O(sigma^d n + n log n) for sets in R^d and O(n log^3 n log log n + k) for sets in the plane, where k is the size of the output.

Algorithms to find the minimum or maximum sigma such that the corresponding graph has properties such as connectivity, planarity, and no-isolated vertex are presented, with complexities in O(n polylog n). These algorithms can also be used to efficiently construct the corresponding graphs.

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 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 Tóth on decompositions of space coverings.

A family of proximity graphs, called Empty Region Graphs (ERG) is presented. The vertices of an ERG are points in the plane, and two points are connected if their neighborhood, defined by a region, does not contain any other point. The region defining the neighborhood of two points is a parameter of the graph. This way of defining graphs is not new, and ERGs include several known proximity graphs such as Nearest Neighbor Graphs, Beta-Skeletons or Theta-Graphs. The main contribution is to provide insight and connections between the definition of ERG and the properties of the corresponding graphs.

We give conditions on the region defining an ERG to ensure a number of properties that might be desirable in applications, such as planarity, connectivity, triangle-freeness, cycle-freeness, bipartiteness and bounded degree. These conditions take the form of what we call tight regions: maximal or minimal regions that a region must contain or be contained in to make the graph satisfy a given property. We show that every monotone property has at least one corresponding tight region; we discuss possibilities and limitations of this general model for constructing a graph from a point set.

We consider algorithms for finding the optimal location of a simple transportation device, that we call a "moving walkway", consisting of a pair of points in the plane between which the travel speed is high. More specifically, one can travel from one endpoint of the walkway to the other at speed v>1, but can only travel at unit speed between any other pair of points. The travel time between any two points in the plane is the minimum between the actual geometric distance, and the time needed to go from one point to the other using the walkway. A location for a walkway is said to be optimal with respect to a given finite set of points if it minimizes the maximum travel time between any two points of the set. We give a simple linear-time algorithm for finding an optimal location in the case where the points are on a line. We also give an Omega(n log n) lower bound for the problem of computing the travel time diameter of a set of n points on a line with respect to a given walkway. Then we describe an O(n log n) algorithm for locating a walkway with the additional restriction that the walkway must be horizontal. This algorithm is based on a recent generic method for solving quasiconvex programs with implicitly defined constraints. It is used in a (1+epsilon)-approximation algorithm for optimal location of a walkway of arbitrary orientation.

We investigate the global scheduling of sporadic, implicit deadline, real-time task systems on multiprocessor platforms. We provide a task model which integrates job parallelism. We prove that the time-complexity of the feasibility problem of these systems is linear relatively to the number of (sporadic) tasks for a fixed number of processors. We propose a scheduling algorithm theoretically optimal (i.e., preemptions and migrations neglected). Moreover, we provide an exact feasibility utilization bound. Lastly, we propose a technique to limit the number of migrations and preemptions.

We propose a definition of locality for properties of geometric graphs. We measure the local density of graphs using region-counting distances between pairs of vertices, and we use this density to define local properties of classes of graphs.

We illustrate locality by introducing the local diameter of geometric graphs: we define it as the upper bound on the size of the shortest path between any pair of vertices, expressed as a function of the density of the graph around these vertices. We determine the local diameter of several well-studied graphs such as Theta-graphs, Ordered Theta-graphs and Skip List Spanners. We also show that various operations, such as path and point queries using geometric graphs as data structures, have complexities which can be expressed as local properties.