Given an arrangement of lines in the plane, what is the minimum number c of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c both for the above question, as well as some of its variations. We redefine these problems as geometric hypergraph coloring problems. If we define as the hypergraph where vertices are lines and edges represent cells of the arrangement, the answer to the above question is equal to the chromatic number of this hypergraph. We prove that this chromatic number is between Ω(logn / loglogn). and O(sqrt(n)). Similarly, we give bounds on the minimum size of a subset S of the intersections of the lines in A such that every cell is bounded by at least one of the vertices in S. This may be seen as a problem on guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph , the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the hypergraph.

We present a general method for de-amortizing essentially any Binary Search Tree (BST) algorithm. In particular, by transforming Splay Trees, our method produces a BST that has the same asymptotic cost as Splay Trees on any access sequence while performing each search in O(logn) worst case time. By transforming Multi-Splay Trees, we obtain a BST that is O(loglogn) competitive, satisfies the scanning theorem, the static optimality theorem, the static finger theorem, the working set theorem, and performs each search in O(logn) worst case time. Moreover, we prove that if there is a dynamically optimal BST algorithm, then there is a dynamically optimal BST algorithm that answers every search in O(logn) worst case time.

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 present a general method for de-amortizing essentially any Binary Search Tree (BST) algorithm. In particular, by transforming Splay Trees, our method produces a BST that has the same asymptotic cost as Splay Trees on any access sequence while performing each search in O(logn) worst case time. By transforming Multi-Splay Trees, we obtain a BST that is O(loglogn) competitive, satisfies the scanning theorem, the static optimality theorem, the static finger theorem, the working set theorem, and performs each search in O(logn) worst case time. Moreover, we prove that if there is a dynamically optimal BST algorithm, then there is a dynamically optimal BST algorithm that answers every search in O(logn) worst case time.

This paper studies problems related to visibility among points in the plane. A point x blocks two points v and w if x is in the interior of the line segment vw. A set of points P is k-blocked if each point in P is assigned one of k colours, such that distinct points v,winP are assigned the same colour if and only if some other point in P blocks v and w. The focus of this paper is the conjecture that each k-blocked set has bounded size (as a function of k). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterise all sets {n₁,n₂,n₃,n₄} such that some 4-blocked set has exactly n_i points in the i-th colour class. Amongst other results, for infinitely many values of k, we construct k-blocked sets with k^1.79... points.

We consider the theoretical model of Crystalline robots, which have been introduced and prototyped by the robotics community. These robots consist of independently manipulable unit-square atoms that can extend/contract arms on each side and attach/detach from neighbors. These operations suffice to reconfigure between any two given (connected) shapes. The worst-case number of sequential moves required to transform one connected configuration to another is known to be Theta(n). 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(nlogn). The result is the first (theoretically) almost-instantaneous universally reconfigurable robot built from simple units.

In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We combine two different approaches to find regular polygons, depending on their number of edges. Our result depends on the parameter alpha, which has been used to bound the maximum number of isosceles triangles that can be formed by n points. This bound has been expressed as O(n^2+2alpha+epsilon), and the current best value for alpha is  0.068. Our algorithm finds polygons with O(n^alpha) edges by sweeping a line through the set of points, while larger polygons are found by random sampling. We can find all regular polygons with high probability in O(n^2+alpha+epsilon) expected time for every positive epsilon. This compares well to the O(n^2+2alpha+epsilon) deterministic algorithm of Brass.

Given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing enough points contains all colors. The goal is to bound the necessary size of such a strip, as a function of k. We show that if the strip size is at least 2k-1, such a coloring can always be found. We prove that the size of the strip is also bounded in any fixed number of dimensions. In contrast to the planar case, we show that deciding whether a 3D point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete.

We also consider the problem of coloring a given set of axis-aligned strips, so that any sufficiently covered point in the plane is covered by k colors. We show that in d dimensions the required coverage is at most d(k-1)+1.

Lower bounds are given for the two problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. Finally, we study a variant where strips are replaced by wedges.

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].

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.

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 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 variant of Cauchy's Lemma, proving that when a convex chain on one sphere is redrawn (with the same lengths and angles) on a larger sphere, the distance between its endpoints increases. The main focus of this work is a comparison of three alternate proofs, to show the links between Toponogov's Comparison Theorem, Legendre's Theorem and Cauchy's Arm Lemma.

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 study a simple geometric model of transportation facility that consists of two points between which the travel speed is high. This elementary definition can model shuttle services, tunnels, bridges, teleportation devices, escalators or moving walkways. The travel time between a pair of points is defined as a time distance, in such a way that a customer uses the transportation facility only if it is helpful. We give algorithms for finding the optimal location of such a transportation facility, where optimality is defined with respect to the maximum travel time between two points in a given set.