Abstract Let $$P=\{p_0,\ldots ,p_{n-1}\}$$ P = { p 0 , … , p n - 1 } be a set of points in $${\mathbb R}^d$$ R d , modeling devices in a wireless network. A range assignment assigns a range $$r(p_i)$$ r ( p i ) to each point $$p_i\in P$$ p i ∈ P , thus inducing a directed communication graph $$\mathcal {G}_r$$ G r in which there is a directed edge $$(p_i,p_j)$$ ( p i , p j ) iff $${{\,\textrm{dist}\,}}(p_i, p_j) \leqslant r(p_i)$$ dist ( p i , p j ) ⩽ r ( p i ) , where $${{\,\textrm{dist}\,}}(p_i,p_j)$$ dist ( p i , p j ) denotes the distance between $$p_i$$ p i and $$p_j$$ p j . The range-assignment problem is to assign the transmission ranges such that $$\mathcal {G}_r$$ G r has a certain desirable property, while minimizing the cost of the assignment; here the cost is given by $$\sum _{p_i\in P} r(p_i)^{\alpha }$$ ∑ p i ∈ P r ( p i ) α , for some constant $$\alpha >1$$ α > 1 called the distance-power gradient. We introduce the online version of the range-assignment problem, where the points $$p_j$$ p j arrive one by one, and the range assignment has to be updated at each arrival. Following the standard in online algorithms, resources given out cannot be taken away—in our case this means that the transmission ranges will never decrease. The property we want to maintain is that $$\mathcal {G}_r$$ G r has a broadcast tree rooted at the first point

We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O ( min ⁡ ( n ω , n 2 + n h log ⁡ h + χ 2 ) ) time, where ω < 2.373 denotes the matrix multiplication exponent and χ ∈ Ω ( n ) ∩ O ( n 2 ) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O ( n 2 log ⁡ n ) time.

Let P = {p₀,…,p_{n-1}} be a set of points in ℝ^d, modeling devices in a wireless network. A range assignment assigns a range r(p_i) to each point p_i ∈ P, thus inducing a directed communication graph 𝒢_r in which there is a directed edge (p_i,p_j) iff dist(p_i, p_j) ⩽ r(p_i), where dist(p_i,p_j) denotes the distance between p_i and p_j. The range-assignment problem is to assign the transmission ranges such that 𝒢_r has a certain desirable property, while minimizing the cost of the assignment; here the cost is given by ∑_{p_i ∈ P} r(p_i)^α, for some constant α > 1 called the distance-power gradient. We introduce the online version of the range-assignment problem, where the points p_j arrive one by one, and the range assignment has to be updated at each arrival. Following the standard in online algorithms, resources given out cannot be taken away - in our case this means that the transmission ranges will never decrease. The property we want to maintain is that 𝒢_r has a broadcast tree rooted at the first point p₀. Our results include the following. - We prove that already in ℝ¹, a 1-competitive algorithm does not exist. In particular, for distance-power gradient α = 2 any online algorithm has competitive ratio at least 1.57. - For points in ℝ¹ and ℝ², we analyze two natural strategies for updating the range assignment upon the arrival of a new point p_j. The strategies do not change the assignment if p_j is already within range of an existing point, otherwise they increase the range of a single point, as follows: Nearest-Neighbor (NN) increases the range of NN(p_j), the nearest neighbor of p_j, to dist(p_j, NN(p_j)), and Cheapest Increase (CI) increases the range of the point p_i for which the resulting cost increase to be able to reach the new point p_j is minimal. We give lower and upper bounds on the competitive ratio of these strategies as a function of the distance-power gradient α. We also analyze the following variant of NN in ℝ² for α = 2: 2-Nearest-Neighbor (2-NN) increases the range of NN(p_j) to 2⋅ dist(p_j,NN(p_j)), - We generalize the problem to points in arbitrary metric spaces, where we present an O(log n)-competitive algorithm.

Abstract It is well known that any set of n intervals in $$\mathbb {R} ^1$$ R1 admits a non-monochromatic coloring with two colors and a conflict-free coloring with three colors. We investigate generalizations of this result to colorings of objects in more complex 1-dimensional spaces, namely so-called tree spaces and planar network spaces.

By folding the free-space diagram for efficient preprocessing, we show that the Frechet distance between 1D curves can be computed in O(nk log n) time, assuming one curve has ply k.

We study dynamic conflict-free colorings in the plane, where the goal is to maintain a conflict-free coloring (CF-coloring for short) under insertions and deletions. - First we consider CF-colorings of a set S of unit squares with respect to points. Our method maintains a CF-coloring that uses O(log n) colors at any time, where n is the current number of squares in S, at the cost of only O(log n) recolorings per insertion or deletion We generalize the method to rectangles whose sides have lengths in the range [1, c], where c is a fixed constant. Here the number of used colors becomes O(log^2 n). The method also extends to arbitrary rectangles whose coordinates come from a fixed universe of size N, yielding O(log^2 N log^2 n) colors. The number of recolorings for both methods stays in O(log n). - We then present a general framework to maintain a CF-coloring under insertions for sets of objects that admit a unimax coloring with a small number of colors in the static case. As an application we show how to maintain a CF-coloring with O(log^3 n) colors for disks (or other objects with linear union complexity) with respect to points at the cost of O(log n) recolorings per insertion. We extend the framework to the fully-dynamic case when the static unimax coloring admits weak deletions. As an application we show how to maintain a CF-coloring with O(sqrt(n) log^2 n) colors for points with respect to rectangles, at the cost of O(log n) recolorings per insertion and O(1) recolorings per deletion. These are the first results on fully-dynamic CF-colorings in the plane, and the first results for semi-dynamic CF-colorings for non-congruent objects.

We introduce the dynamic conflict-free coloring problem for a set S of intervals in R 1 with respect to points, where the goal is to maintain a conflict-free coloring for S under insertions and deletions. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include: - a lower bound on the number of recolorings as a function of the number of colors, which implies that with O(1) recolorings per update the worst-case number of colors is Ω(logn/loglogn) , and that any strategy using O(1/ε) colors needs Ω(εn ε ) recolorings; - a coloring strategy that uses O(logn) colors at the cost of O(logn) recolorings, and another strategy that uses O(1/ε) colors at the cost of O(n ε /ε) recolorings; - stronger upper and lower bounds for special cases. We also consider the kinetic setting where the intervals move continuously (but there are no insertions or deletions); here we show how to maintain a coloring with only four colors at the cost of three recolorings per event and show this is tight.