We consider the fundamental problem of assigning distinct labels to agents in theprobabilistic model of population protocols. Our protocols operate under the assumptionthat the size n of the population is embedded in the transition function. W.h.p. (withhigh probability), they are silent, i.e., eventually each agent reaches its nal state andremains in it forever, and they are safe, i.e., never change a label that has already beenassigned to an agent. We provide efficient protocols for this problem complemented withtight lower bounds. Our fast labeling protocol uses only O((n logn)/ε) interactions w.h.p.,(2 + ε)n + O(na) states, and the label range [1,(1 + ε)n], where 1 ≥ ε > 0 and 0 < a < 1,while our nearly state-optimal protocol uses only n + 5√n + O(log logn) states, the labelrange [1,n], and w.h.p., O(n3) interactions.

We study the problems of computing the Voronoi diagram and a triangulation of a set of n 2 points with O ( log ⁡ n ) -bit coordinates in the Euclidean plane in a substantially sublinear in n number of rounds in the congested clique model with n nodes. First, we observe that if the points are uniformly at random distributed in a unit square then their Voronoi diagram within the square can be computed in O ( 1 ) rounds with high probability (w.h.p.). Next, we show that if a very weak smoothness condition is satisfied by an input set of n 2 points with O ( log ⁡ n ) -bit coordinates in the unit square then the Voronoi diagram of the point set within the unit square can be deterministically computed in O ( log ⁡ n ) rounds in this model. Finally, we present a deterministic O ( log ⁡ n ) -round protocol for a triangulation of n 2 points with O ( log ⁡ n ) -bit coordinates in the Euclidean plane. It relies on our novel method for extending triangulations of two planar point sets separated by a straight line to a complete triangulation of the union of the sets in O ( 1 ) rounds.

Abstract Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin (SIAM J Comput 33(4):937–951, 2004) showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have $$\varOmega (n)$$ Ω ( n ) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy.

We consider the fundamental problem of assigning distinct labels to agents in the probabilistic model of population protocols. Our protocols operate under the assumption that the size n of the population is embedded in the transition function. Their efficiency is expressed in terms of the number of states utilized by agents, the size of the range from which the labels are drawn, and the expected number of interactions required by our solutions. Our primary goal is to provide efficient protocols for this fundamental problem complemented with tight lower bounds in all the three aspects. W.h.p. (with high probability), our labeling protocols are silent, i.e., eventually each agent reaches its final state and remains in it forever, and they are safe, i.e., never update the label assigned to any single agent. We first present a silent w.h.p. and safe labeling protocol that draws labels from the range [1,2n]. Both the number of interactions required and the number of states used by the protocol are asymptotically optimal, i.e., O(n log n) w.h.p. and O(n), respectively. Next, we present a generalization of the protocol, where the range of assigned labels is [1,(1+ε) n]. The generalized protocol requires O(n log n / ε) interactions in order to complete the assignment of distinct labels from [1,(1+ε) n] to the n agents, w.h.p. It is also silent w.h.p. and safe, and uses (2+ε)n+O(n^c) states, for any positive c < 1. On the other hand, we consider the so-called pool labeling protocols that include our fast protocols. We show that the expected number of interactions required by any pool protocol is ≥ (n²)/(r+1), when the labels range is 1,… , n+r < 2n. Furthermore, we provide a protocol which uses only n+5√ n +O(n^c) states, for any c < 1, and draws labels from the range 1,… ,n. The expected number of interactions required by the protocol is O(n³). Once a unique leader is elected it produces a valid labeling and it is silent and safe. On the other hand, we show that (even if a unique leader is given in advance) any silent protocol that produces a valid labeling and is safe with probability > 1-(1/n), uses ≥ n+√{(n-1)/2}-1 states. Hence, our protocol is almost state-optimal. We also present a generalization of the protocol to include a trade-off between the number of states and the expected number of interactions. Finally, we show that for any silent and safe labeling protocol utilizing n+t < 2n states, the expected number of interactions required to achieve a valid labeling is ≥ (n²)/(t+1).

Let C be the unit circle in R^2. We can view C as a plane graph whose vertices are all the points on C, and the distance between any two points on C is the length of the smaller arc between them. We consider a graph augmentation problem on C, where we want to place k >= 1 shortcuts on C such that the diameter of the resulting graph is minimized. We analyze for each k with 1 <= k <= 7 what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of k. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is 2 + Theta(1/k^(2/3)) for any k.

We study the problem of efficiently correcting an erroneous product of two $$n\times n$$ matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most k erroneous entries running in $${\tilde{O}}(n^2+kn)$$ time and a deterministic $${\tilde{O}}(kn^2)$$ -time algorithm for this problem (where the notation $${\tilde{O}}$$ suppresses polylogarithmic terms in n and k).

Suppose that a circular fire spreads in the plane at unit speed. A fire fighter can build a barrier at speed v > 1. How large must v be to ensure that the fire can be contained, and how should the fire fighter proceed? We provide two results. First, we analyze the natural strategy where the fighter keeps building a barrier along the frontier of the expanding fire. We prove that this approach contains the fire if v > v_c = 2.6144... holds. Second, we show that any "spiralling" strategy must have speed v > 1.618, the golden ratio, in order to succeed.

Given an arbitrary real constant ε > 0, and a geometric graph G in d -dimensional Euclidean space with n points, O ( n ) edges, and constant dilation, our main result is a data structure that answers (1 + ε)-approximate shortest-path-length queries in constant time. The data structure can be constructed in O ( n log n ) time using O ( n log n ) space. This represents the first data structure that answers (1 + ε)-approximate shortest-path queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortest-path queries between vertices in a planar polygonal domain with “rounded” obstacles can be answered in constant time. Other applications include query versions of closest-pair problems, and the efficient computation of the approximate dilations of geometric graphs. Finally, we show how to extend the main result to answer (1 + ε)-approximate shortest-path-length queries in constant time for geometric spanner graphs with m = ω( n ) edges. The resulting data structure can be constructed in O ( m + n log n ) time using O ( n log n ) space.

Abstract. We consider the problem of computing a minimum weight pseudo-triangulation of a set S of n points in the plane. We first present an O(n log n)-time algorithm that produces a pseudo-triangulation of weight O(wt(M(S)) · log n) which is shown to be asymptotically worstcase optimal, i.e., there exists a point set S for which every pseudotriangulation has weight Ω(log n · wt(M(S))), where wt(M(S)) is the weight of a minimum spanning tree of S. We also present a constant factor approximation algorithm running in cubic time. In the process we give an algorithm that produces a minimum weight pseudo-triangulation of a simple polygon. 1

Given a set V of n points in $\IR^d$ and a real constant t>1, we present the first O(nlog n)-time algorithm to compute a geometric t-spanner on V. A geometric t-spanner on V is a connected graph G = (V,E) with edge weights equal to the Euclidean distances between the endpoints, and with the property that, for all $u,v\in V$, the distance between u and v in G is at most t times the Euclidean distance between u and v. The spanner output by the algorithm has O(n) edges and weight $O(1)\cdot wt(MST)$, and its degree is bounded by a constant.

Let S be a set of n points in lKd, and k m integer such that 1 5 k 5 n -2.Algorithms are given that construct fault-tolerant spanners for S. If in such a spanner at most k edges or vertices are removed, then each pair of points in the remaining graph is still connected by a short path.Our results include (i) an algorithm with running time O(n logdB1 n + kn log log n + k2n) that constructs a spanner with O(k2n) edges, that is resilient to k edge faults, (ii) an algorithm with running time O(n logn + k2n) that constructs a spanner with O(k2n) edges, that is resilient to k vertex faults, and (iii) an algorithm with rllnning time O(n logn+&n) that constructs a spanner of degree O(s), whose total edge length is bounded by G(2) times the weight of a miuimum spanning tree of S, and that is resilient to k edge or vertex faults.Here, c is a constant that is independent of n and Ic.

We consider the problem of partitioning isothetic polygons into rectangles by drawing edges of minimum total length. The problem has various applications [LPRS], eg. in VLSI design when dividing routing regions into channels ([Riv1], [Riv2]). If the polygons contain holes, the problem in NP-hard [LPRS]. In this paper it is shown how solutions within a constant factor of the optimum can be computed in time Ο(n log n), thus improving the previous Ο(n2) time bound. An unusual divide-and-conquer technique is employed, involving alternating search from two opposite directions, and further efficiency is gained by using a fast method to sort subsets of points. Generalized Voronoi diagrams are used in combination with plane-sweeping in order to detect all “well bounded” rectangles, which are essential for the heuristic.