Oswin Aichholzer

Sergio Cabello

Ruy Fabila-Monroy

David Flores-Peñaloza

Thomas Hackl

Clemens Huemer

Ferran Hurtado

David R Wood

Edge-Removal and Non-Crossing Configurations in Geometric Graphs ¶

Keywords: extremal graph theory, geometric graph, perfect matching, spanning tree

A geometric graph is a graph G = (V, E) drawn in the plane, such that V is a point set in general position and E is a set of straight-line segments whose endpoints belong to V . We study the following extremal problem for geometric graphs: How many arbitrary edges can be removed from a complete geometric graph with n vertices such that the remaining graph still contains a certain non-crossing subgraph. The non-crossing subgraphs that we consider are perfect matchings, subtrees of a given size, and triangulations. In each case, we obtain tight bounds on the maximum number of removable edges.

Introduction

A geometric graph is a graph G = (V, E) drawn in the plane, such that V is a point set in general position (meaning that no three points of V lie on a common line) and E is a set of straight-line segments whose endpoints belong to V . A convex graph is a geometric graph whose vertex set is in convex position. A geometric graph is called non-crossing if no two edges intersect in their interior, but two edges might have an endpoint in common. Two edges are disjoint if they have no point in common.

Extremal problems for geometric graphs have received considerable attention. One such problem is to determine the minimum integer e k (n) such that every geometric graph with n vertices and m > e k (n) edges contains k + 1 pairwise disjoint edges. Equivalently, e k (n) is the maximum number of edges in a geometric graph with n vertices and no k + 1 pairwise disjoint edges.

This problem was first studied by Erdős [START_REF] Erdős | On sets of distances of n points[END_REF], Perles, Kupitz, and Avital and Hanani. Accounts of the history of this topic can be found in [START_REF] Alon | Disjoint edges in geometric graphs[END_REF][START_REF] Černý | Geometric graphs with no three disjoint edges[END_REF][START_REF] Felsner | Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry[END_REF][START_REF] Pach | Geometric graph theory[END_REF]. Erdős [START_REF] Erdős | On sets of distances of n points[END_REF] proved that e 1 (n) = n. (This result solves Conway's thrackle conjecture for straight-line thrackles.) For three pairwise disjoint edges, bounds on e 2 (n) were given in [START_REF] Alon | Disjoint edges in geometric graphs[END_REF][START_REF] Goddard | Forcing disjoint segments in the plane[END_REF], culminating in e 2 (n) = 5 2 n plus a constant, as shown recently by Černý [START_REF] Černý | Geometric graphs with no three disjoint edges[END_REF]. Bounds on e 3 (n) have been obtained in [START_REF] Goddard | Forcing disjoint segments in the plane[END_REF][START_REF] Tóth | Geometric graphs with few disjoint edges[END_REF].

For general values of k, Goddard et al. [START_REF] Goddard | Forcing disjoint segments in the plane[END_REF] showed that e k (n) ≤ cn(log n) k-4 for some constant c. This was improved by Pach and Törőcsik [START_REF] Pach | Some geometric applications of Dilworth's theorem[END_REF] to e k (n) ≤ k 4 n, the first upper bound linear in n. Tóth and Valtr [START_REF] Tóth | Geometric graphs with few disjoint edges[END_REF] improved the dependence on k to e k (n) ≤ k 3 (n + 1). This bound was improved (for k ≥ 2 9 ) to e k (n) ≤ 2 9 k 2 n by Tóth [START_REF] Tóth | Note on geometric graphs[END_REF], where the constant 2 9 has since been improved to 2 8 by Felsner [START_REF] Felsner | Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry[END_REF]. Kupitz proved a lower bound of e k (n) > kn, which was improved to e k (n) ≥ 3 2 (k -1)n -2k 2 by Tóth and Valtr [START_REF] Tóth | Geometric graphs with few disjoint edges[END_REF]. It is conjectured that e k (n) ≤ ckn for some constant c. Note that for convex graphs, this question was completely settled by Kupitz and Perles for each k. They showed that every convex graph with n vertices and at least kn + 1 edges contains k + 1 pairwise disjoint edges, and this bound is tight; see [START_REF] Goddard | Forcing disjoint segments in the plane[END_REF]. Closely related work is [START_REF] Brass | A Turán-type extremal theory of convex geometric graphs[END_REF][START_REF] Károlyi | Ramsey-type results for geometric graphs[END_REF][START_REF] Kupitz | On pairs of disjoint segments in convex position in the plane[END_REF][START_REF] Kupitz | Extremal theory for convex matchings in convex geometric graphs[END_REF].

Our Results

Research on e k (n) has focused on small values of k. But k can be as large as n 2 -1 for even n, which is the case that we study. Our first contribution is to determine e n-1 (2n) for all n. By definition, e n-1 (2n) is the minimum integer such that every geometric graph with 2n vertices and at least e n-1 (2n) + 1 edges contains a non-crossing perfect matching. Equivalently, 2n 2 -(e n-1 (2n) + 1) is the maximum number of arbitrary edges that can be removed from any complete geometric graph, such that the remaining geometric graph still contains a non-crossing perfect matching. We prove that every complete geometric graph on 2n vertices still contains a non-crossing perfect matching after removing any set of n -1 edges. That is, 2n 2 -(e n-1 (2n) + 1) ≥ n -1, implying e n-1 (2n) ≤ 2n 2 -n. This bound is achieved for the complete convex graph, meaning that there exists a set of n edges whose removal disallows a non-crossing perfect matching in the remaining graph. Kupitz and Perles already obtained this bound on the complete convex graph. Hence e n-1 (2n) = 2n 2 -n = 2n(n -1) . These results are presented in Section 2.

Our second contribution is motivated by a closely related problem posed by Micha Perles in 2002 and studied by Černý, Dvořák, Jelínek and Kára [START_REF] Černý | Noncrossing Hamiltonian paths in geometric graphs[END_REF]: How many edges can be removed from a complete geometric graph on n vertices such that the remaining graph still contains a non-crossing Hamiltonian path? It is of interest to study this type of problem for other classes of non-crossing geometric graphs. We consider subtrees of a given size. For the case of spanning trees, removing n -2 arbitrary edges from any complete geometric graph on n vertices leaves a graph that still contains a non-crossing spanning tree [START_REF] Károlyi | Ramsey-type results for geometric graphs[END_REF]. Removal of more edges is possible if the set of removed edges has certain properties. Benediktovich [START_REF] Benediktovich | Plane subgraphs in geometric complement of 2-factor and complete bipartite graph[END_REF] recently showed that every complete geometric graph on n ≥ 5 vertices still contains a non-crossing spanning tree after removing any self-crossing 2-factor (that is, a 2-regular spanning subgraph with two edges sharing an interior point).

We prove that every complete geometric graph on n vertices still contains a non-crossing subtree that spans nk vertices after removing kn 2 arbitrary edges, for k ≥ 2, and this bound is tight. This result is presented in Section 3.

Finally in Section 4, we consider the question of how many edges (not on the boundary of the convex hull) can be removed from a complete geometric graph so that the remaining geometric graph contains a triangulation or a pseudo-triangulation.

In the following, if H is a subgraph of a geometric graph G, then G -H denotes the geometric graph obtained from G by deleting the edges of H. The edges of H are called removed or forbidden edges.

Perfect matchings

In this section we determine the maximum number of arbitrary edges that can be removed from any complete geometric graph such that the remaining geometric graph still contains a non-crossing perfect matching. The proof relies on the following result for abstract graphs. Proof: For each p we prove the theorem by induction on k. For k = 1 the statement is trivial. Assume the statement is true for every number k < k. Now, we are given the complete graph K kp and we are given a spanning subgraph H = (V, E ) with |E | ≤ k -1. Assume that |E | > 0, as otherwise nothing has to be proved. Observe that there exists a set Q of at least p -1 isolated vertices in H and there exists a vertex v / ∈ Q whose degree is at least 1 in H. Let N (v) denote the set of neighbors of v in H. Define a graph H = (V \(Q ∪ {v}), E * ) where E * is obtained by first taking the set of edges of the subgraph of H induced by (V \(Q ∪ {v}), E ) and then adding a minimum number of edges to the resulting set, such that N (v) is connected. We have

|E * | ≤ |E | -1 ≤ k -2, because we removed deg H (v)
edges and added at most deg H (v) -1 edges to restore the connectedness. By induction, K (k-1)p -H contains the complete p-partite graph K k-1,...,k-1 . Since N (v) is connected in H , all the vertices of N (v) belong to the same vertex class of K k-1,...,k-1 . Add v to the vertex class containing N (v), and add one vertex in Q to each of the other vertex classes so that

K k,...,k ⊆ K kp -H. 2
Corollary 2.2 For every complete geometric graph G on 2n vertices and for every subgraph H of G with at most n -1 edges, the geometric graph G -H contains a non-crossing perfect matching. This bound is tight with respect to the cardinality of the set of forbidden edges.

Proof: Apply the case p = 2 of Theorem 2.1, which states that G -H contains a complete bipartite graph K n,n . Color the point set according to this bipartition, say red and blue. This 2-colored point set has a v Fig. 1: Removing n edges from the complete geometric graph on a set of 2n points can disallow a non-crossing perfect matching.

non-crossing red-blue matching; that is, each edge of the matching connects a red and a blue point [START_REF]The 1979 Putnam Exam. The William Lowell Putnam Mathematical Competition problems and solutions : 1965-1984[END_REF]. Thus, this matching does not use edges of H.

Removing n edges from G does not always leave a non-crossing perfect matching, as can be seen in Figure 1 (left). There, if the vertex v is matched to another point not using the drawn 'forbidden' edges, then this segment splits the point set into two sets of odd size, which disallows a non-crossing perfect matching. Thus, the bound of n -1 edges is tight.

2

Another example that prohibits a non-crossing perfect matching without forbidden edges is shown in Figure 1 (right): Remove n consecutive edges from the convex hull of the complete convex graph. Then every non-crossing perfect matching contains at least one of these n forbidden edges. To see this, we use the fact that each non-crossing perfect matching on a point set in convex position has at least two edges of the convex hull [START_REF] Hernando | Graphs of non-crossing perfect matchings[END_REF]. Since the n forbidden edges span n + 1 points, any non-crossing perfect matching would have an edge that connects two of those n + 1 points. However, this edge would split the point set into two smaller point sets, and in one of them all but one edge of the convex hull are forbidden, which means that it cannot have a non-crossing perfect matching. Examples for the convex geometric graph are also due to Kupitz and Perles.

In both examples the graph defined by the forbidden edges has one component that contains n + 1 vertices. The size of the largest component in this graph turns out to be crucial for the existence of a non-crossing perfect matching without forbidden edges. To show this, we first prove a result for colored point sets (which extends a known proof for 2-colored point sets). Theorem 2.3 Let S be a set of colored points in general position in the plane with |S| even. Then S admits a non-crossing perfect matching such that every edge connects two points of distinct colors if and only if at most half the points in S have the same color.

Proof: It is necessary for at most half the points in S to have the same color, as otherwise every perfect matching would connect two points of this color. Now we prove the sufficiency. Say the colors are 1, 2, . . . , l. Let S i be the set of points colored i, for 1 ≤ i ≤ . First, we construct a perfect matching without edges connecting points of the same color, but possibly with edge crossings. Thereto, choose a point from the largest color class S i and match it with a point from some other color class S j . This maintains the property that every color class contains at most half the unmatched points. Continue this process until we obtain a perfect matching. (Note that Sitton [START_REF] Sitton | Maximum matchings in complete multipartite graphs[END_REF] proved a more general result about the size of the largest matching in an arbitrary complete multipartite graph.) Now consider a perfect matching M with minimum total edge length. Suppose for the sake of contradiction that M has a crossing, as illustrated in Figure 2. Observe that the corresponding 4-gon contains at least two pairwise disjoint edges connecting points of different colors (the dotted edges). By replacing the two crossing edges by these two edges of the 4-gon we obtain a perfect matching with shorter total edge length. This contradiction proves that M is non-crossing.

2

Note that a problem related to Theorem 2.3 concerning long alternating paths for multicolored point sets was studied by Merino et al. [START_REF] Merino | On the length of longest alternating paths for multicoloured point sets in convex position[END_REF].

Corollary 2.4 For every complete geometric graph G on 2n vertices, and for every subgraph H of G with at most n vertices in each component, the geometric graph G -H contains a non-crossing perfect matching.

Proof: Color each component with a different color and apply Theorem 2.3. 2

Note that Corollary 2.4 also implies Corollary 2.2.

We believe that if a complete geometric graph has many vertices in the interior of the convex hull (at least about half of the points), then more edges can be removed to still have a non-crossing perfect matching. In Figure 1 (left), k = n -2 points of the 2n points are in the interior of the convex hull and removal of the k + 2 solid edges disallows a non-crossing perfect matching.

Conjecture 1 For every complete geometric graph G on a set of 2n vertices with k ≥ n-2 of them in the interior of the convex hull, and for every subgraph H of G which has at most k + 1 edges, the geometric graph G -H contains a non-crossing perfect matching.

Non-crossing subtrees

In this section we investigate how many arbitrary edges can be removed from a complete geometric graph such that the remaining graph still contains a non-crossing tree of a given size.

The case of spanning trees is a simple corollary of a theorem by Károlyi et al. [START_REF] Károlyi | Ramsey-type results for geometric graphs[END_REF], who proved that for every 2-coloring of the edges of a complete geometric graph G, at least one color class contains a noncrossing spanning tree. Thus, if we color a given set of at most n -2 edges red and the remaining edges blue, then the spanning tree must be blue. That is, if n -2 edges are removed from G, then the remaining graph still contains a non-crossing spanning tree. This bound is tight, since removing the n -1 edges incident to a single vertex disallows any spanning tree. Also, removing n -1 edges from the boundary of the convex hull of the complete convex graph disallows a non-crossing spanning tree. v Fig. 3: Construction of T . Now consider non-crossing trees that span fewer vertices. It turns out that the connectivity of the removed subgraph H is crucial for the size of the largest non-crossing subtree. Recall that a graph H is k-connected if H has at least k + 1 vertices and every cut has at least k vertices, where a cut is a set of vertices whose removal disconnects H. The connectivity of H is the maximum integer k such that H is k-connected. Lemma 3.1 For every complete geometric graph G on n vertices and for every spanning subgraph H of G with connectivity k, the geometric graph G -H contains a non-crossing subtree that spans nk vertices. Moreover, there is a spanning subgraph H of G with connectivity k, such that every subtree of G -H has at most nk vertices.

Proof: Since H is k-connected, it has at least k + 1 vertices. If H has exactly k + 1 vertices, then G -H contains K n-k as a subgraph, which contains a non-crossing spanning tree on n-k vertices. Now assume that H has at least k + 2 vertices. Thus H has a cut set X with k vertices. The graph obtained from H by deleting the vertices in X has at least two components. Color the vertices in one component red and color the remaining vertices (not in X) blue. Choose a red vertex v. We now construct a non-crossing tree T , as illustrated in Figure 3. First connect v to every blue vertex. This defines a non-crossing star. Extend each edge of the star to an infinite ray starting at v. These rays divide the plane into regions. If the angle of one such region at v is greater than π, then draw one auxiliary ray at v in this region, so that the angle of each region at v is at most π. Thus each region is convex. Each red point except v lies inside one of these regions. For each region, choose a blue point on its boundary, which exists by construction. Connect in T every red point in that region to the chosen blue point. Within each region T is a non-crossing star. Thus T is a non-crossing tree on at least nk vertices, in which each edge connects a red and a blue vertex. Hence T does not use edges of H. To prove the final claim, let H be the subgraph consisting of every edge incident to k arbitrary vertices. It is easily seen that H has connectivity k. Since G -H is isomorphic to K n-k plus k isolated vertices, every subtree of G -H has at most nk vertices.

2

In particular, Lemma 3.1 implies that for every subgraph H with n -1 edges of a complete geometric graph G on n vertices, the geometric graph G -H contains a non-crossing subtree that spans n -1 vertices. Also, for every disconnected subgraph H of a complete geometric graph G, the geometric graph G -H contains a non-crossing spanning tree.

For a convex graph G with n vertices, number the vertices 0, 1, . . . , n -1 in counterclockwise order. The depth of an edge ij is defined to be min{|i -j|, n -|i -j|}. Edges on the boundary of the convex hull thus have depth 1. Edges with depth 2 are called ears. Theorem 3.2 For 2 ≤ k ≤ n -1, for every complete geometric graph G on n vertices, and for every subgraph H of G with at most kn/2 -1 edges, the geometric graph G -H contains a non-crossing subtree that spans nk + 1 vertices. This bound is tight with respect to the cardinality of the set of forbidden edges: the complete convex graph G has a subgraph H with kn/2 edges such that every non-crossing tree in G -H has at most nk vertices.

Proof: Since H has at most kn/2 -1 edges, v∈H deg(v) ≤ 2 ( kn/2 -1) ≤ kn -1 .
Therefore, the average vertex degree is less than k. Consequently there exists a vertex in H of degree at most k -1 in H and thus the connectivity of H is at most k -1. By Lemma 3.1, G-H has a non-crossing subtree that spans at least nk + 1 vertices.

We now show that the complete convex graph G with n vertices has a subgraph H with kn/2 edges such that G-H has no non-crossing tree on n-k +1 vertices. The subgraph H is the Harary graph H k,n [START_REF] Harary | The maximum connectivity of a graph[END_REF]. We now define this graph, and draw it as a convex graph with its vertices numbered 0, 1, . . . , n -1 in counterclockwise order (see Figure 4). First every edge with depth at most k/2 is in H k,n . This adds 2 k/2 edges incident to each vertex. If k is odd, then in addition every edge ij with |i -j| = n/2 is in H k,n . This adds one edge incident to each vertex, except for odd n, in which case the vertex (n -1)/2 gets two more incident edges. It follows that H k,n has kn/2 edges in all cases. Suppose on the contrary that there is a non-crossing tree T in G -H k,n with t ≥ nk + 1 vertices. Consider the dual graph D of T , which contains one vertex for each region that is bounded by edges of T and the boundary of the convex hull (excluding the region outside the convex hull of G). Two vertices of D are adjacent if the corresponding regions share an edge of T . It is well known that D is a tree.

An edge of T on the boundary of the convex hull of T is called a boundary edge. Each boundary edge with depth d forces T to avoid a distinct set of d -1 vertices. Since T avoids H k,n , each edge in T has depth at least k/2 + 1. So if T has b boundary edges, then T has at most nb k/2 vertices. Thus nk + 1 ≤ t ≤ nb k/2 . García et al. [START_REF] García | Packing trees into planar graphs[END_REF] proved that every convex straight-line drawing of a tree has at least two boundary edges. Thus b ≥ 2, implying b = 2, k is odd, and t = nk + 1. Moreover, García et al. [START_REF] García | Packing trees into planar graphs[END_REF] proved that every tree that admits a convex straight-line drawing with only two boundary edges is a caterpillar, and in this case the dual is a path. Thus T is a caterpillar and D is a path. As illustrated in Figure 5, T has exactly two edges f and f of depth (k + 1)/2, the endpoints of D correspond to the regions defined by f and f , and each such region contains (k -1)/2 vertices not in T . Every other vertex is in T . Define the function q as follows. For each edge e of D, if ij is the edge of T that crosses e, then let q(e) := |i-j|. Below we prove that q(e) = n/2 for some edge e of D. This implies that |i-j| = n/2 for some edge ij of T , which is a contradiction since every such edge is in H k,n .

We now consider two cases depending on whether vertex 0 borders one of the regions defined by f and f . First suppose that 0 borders the region corresponding to f , as illustrated in Figure 5 (left). In this case, walking along D starting from the edge that crosses f , the function q starts at (k + 1)/2, increases by 1 at each step, up to n -(k + 1)/2. Thus q(e) = n/2 for some edge e of D. The case in which 0 borders the region corresponding to f is analogous. Now assume that 0 borders neither region, as illustrated in Figure 5 (right). Let v be the neighbor of 0 with maximum index. Thus v is adjacent to n -1 in T . Let α be the edge of D that crosses the edge {0, v} of T . Let β be the edge of D that crosses the edge {v, n -1} of T . First suppose that v ≥ n/2 . Then walking along D starting from α in the direction away from β, the function q starts at v, decreases by 1 at each step, down to (k + 1)/2. Thus q(e) = n/2 for some edge e of D. Now assume that v ≤ n/2 -1. Then walking along D starting from β in the direction away from α, the function q starts at n -1 -v (which is at least n/2 ), then decreases by 1 at each step, down to (k + 1)/2. Thus q(e) = n/2 for some edge e of D. 2

Point sets with many interior points

We now present point sets with many interior points such that it is not possible to remove more edges than in the convex case to guarantee a non-crossing subtree of a given size in the remaining graph; cf. Theorem 3.2 with k = 2(l + 1) and n = h(l + 1).

Proposition 3.3 For all h ≥ 3 and l ≥ 0, there exists a point set S with h exterior and • h interior points, and a subgraph H of the complete geometric graph G on S with ( + 1) 2 • h edges such that every non-crossing subtree of the geometric graph G -H spans at most (l + 1)h -2(l + 1) vertices.

Proof: To construct S take the vertices of a regular h-gon and place k = •h interior points on the incircle of the h-gon, in such a way that the interior points are distributed in groups of equal size . Each group of points is placed "very close" to a different edge of the h-gon. Within each group the distance from the points to the corresponding edge of the h-gon is monotonically increasing when considering the points in the counterclockwise order they are encountered along the incircle. Let G be the complete geometric graph with vertex set S. Figure 6 (left) depicts the situation. Let S be the set of points in convex position obtained from S by moving each interior point in S to the circumcircle of the h-gon, as indicated in Figure 6 (right). Let G be the complete geometric graph with vertex set S . Let H be the Harary graph H 2( +1),( +1)•h defined with respect to S . Consider H to also be a subgraph of G.

Observe that each edge-crossing produced by moving the interior points from the incircle to the circumcircle involves an edge connecting an interior point to its nearest vertex of the h-gon or involves an edge of the h-gon (the solid edges in Figure 6). Each such edge has depth at most l + 1 in G . Each such edge is in H, since by the definition of the Harary graph with k = 2(l + 1), every edge of depth at most l + 1 = k/2 is in H. Thus every non-crossing subtree in G -H is a non-crossing subtree in G -H. Since every non-crossing subtree in G -H has at most (l + 1)h -2(l + 1) vertices (by Theorem 3.2), every non-crossing subtree in G -H has at most (l + 1)h -2(l + 1) vertices. 2

Triangulations and pseudo-triangulations

This section considers how many edges can be removed from a complete geometric graph so that the remaining geometric graph contains a triangulation or a pseudo-triangulation. In a related work, Lloyd [START_REF] Lloyd | On triangulations of a set of points in the plane[END_REF] proved that it is NP-complete to decide whether a given geometric graph contains a triangulation of its vertex set. In every complete geometric graph G = (V, E), there are edges of G, such as those on the boundary of the convex hull, that appear in every triangulation of V . We call these edges unavoidable, and it is easy to see that an edge e is unavoidable if and only if there exists no edge e that crosses e. Every other edge is called avoidable. Since removing only one unavoidable edge disallows a triangulation, we only consider avoidable edges for removal.

First consider the convex case. Since every edge not on the boundary of the convex hull is crossed by some other edge (for n ≥ 4), an edge of the complete convex graph is unavoidable if and only if it is on the boundary of the convex hull. Proof: We proceed by induction on the number of vertices. For n ≤ 4 the statement is trivial. Assume the statement holds for each n < n and that E = ∅. Recall that an ear is an edge of G with depth 2.

If no ear is in E , then let f be any edge in E , and let e be an ear that crosses f . Otherwise, some ear is in E . Since there are n ears, and |E | < n, there are 'consecutive' ears e and f that cross, such that e ∈ E and f ∈ E . In both cases, there is an ear e ∈ E that crosses an edge f ∈ E .

Let v be the vertex adjacent to both endpoints of e. Then f is incident to v. So Hv has at least one less forbidden edge than H. Thus we can apply induction with v removed. We obtain a triangulation in (Gv) -H. Adding e and the two boundary edges incident to v (which are unavoidable), we obtain the desired triangulation in G -H.

To see that removing n -2 edges can disallow a triangulation, delete an ear e and all n -3 edges that cross e. 2

If we allow interior points, then fewer edges can be removed to disallow a triangulation.

Proposition 4.2 There exist point sets with interior points, such that removing two avoidable edges disallows a triangulation.

Proof: Figure 7 (left) shows an example. Observe that for every interior point of a triangulation and for every straight-line passing through this point, there must be edges incident to that point on both sides of the line. In the example, there are exactly two edges to the left of the line through the interior point. Thus at least one of these two edges is in every triangulation. And removing these two edges disallows a triangulation. 2 Proposition 4.2 is best possible, because by definition, every avoidable edge is in some triangulation. We finally consider pseudo-triangulations. A pseudo-triangle is a simple polygon that has exactly three interior angles less than π. A pseudo-triangulation of a point set S is a partition of the convex hull of S into pseudo-triangles whose vertex set is exactly S. Note that for point sets in convex position, triangulations and pseudo-triangulations coincide. For the question considered in Proposition 4.2, pseudo-triangulations behave similarly to triangulations. Proposition 4.3 There exist point sets with interior points, such that removing four avoidable edges disallows a pseudo-triangulation.

Proof: Figure 7 (right) shows an example. The four solid edges are avoidable. To see that their removal disallows a pseudo-triangulation, observe that the face incident to the interior vertex with angle greater than π has to have at least four convex vertices, whereas a pseudo-triangle has exactly three.

2

Theorem 2 . 1

 21 For all p ≥ 2, for every spanning subgraph H = (V, E ) of the complete graph K kp with |E | ≤ k -1, the graph K kp -H contains the complete p-partite graph K k,...,k .

Fig. 2 :

 2 Fig. 2: Crossing removal.

Fig. 4 :

 4 Fig. 4: The Harary graphs H4,10, H5,10 and H5,11.

Fig. 5 :

 5 Fig.5: The caterpillar T , its dual graph D (bold), and the forbidden edges (dashed).

Fig. 6 :

 6 Fig. 6: Illustration for the proof of Proposition 3.3 with h = 4 and l = 3.

Theorem 4 . 1

 41 For each subgraph H = (V, E ) of the complete convex graph G on n ≥ 3 vertices, where E is a set of at most n -3 avoidable edges, the convex graph G -H contains a triangulation. This bound is tight with respect to |E |.

Fig. 7 :

 7 Fig. 7: Removing two avoidable edges disallows a triangulation (left), and removing four avoidable edges disallows a pseudo-triangulation (right).

Acknowledgements

We thank the anonymous referees for pointing out some relevant references.

* Supported by the Austrian FWF National Research Network 'Industrial Geometry' S9205-N12. † Supported by the Slovenian Research Agency, project J1-7218. ‡ Supported by projects MEC MTM2006-01267, MEC MTM2009-07242 and Gen. Cat. 2005SGR00692, Gen. Cat. DGR 2009SGR1040. § Supported by a QEII Research Fellowship from the Australian Research Council. Research completed at the Universitat Politècnica de Catalunya, where supported by the Marie Curie Fellowship 023865, and by the projects MEC MTM2006-01267 and Gen. Cat. 2005SGR00692. 1365-8050


James Currie
email: j.currie@uwinnipeg.ca

Narad Rampersad
email: n.rampersad@uwinnipeg.ca

Cubefree words with many squares

Keywords:

We construct infinite cubefree binary words containing exponentially many distinct squares of length n. We also show that for every positive integer n, there is a cubefree binary square of length 2n.

Introduction

A square is a non-empty word of the form xx, and a cube is a non-empty word of the form xxx. An overlap is a word of the form axaxa, where a is a letter and x is a word (possibly empty). A word is squarefree (resp. cubefree, overlap-free) if none of its factors are squares (resp. cubes, overlaps). For further background material concerning combinatorics on words we refer the reader to [START_REF] Allouche | Automatic Sequences: Theory, Applications, Generalizations[END_REF].

It is well-known that there exist infinite squarefree words over a ternary alphabet and infinite overlapfree words over a binary alphabet. Clearly, any overlap-free word is also cubefree. Any infinite cubefree binary word must contain squares; however, Dekking [START_REF] Dekking | On repetitions of blocks in binary sequences[END_REF] proved that there exists an infinite cubefree binary word containing no squares xx where the length of x is greater than 3 (see also [START_REF] Rampersad | Avoiding large squares in infinite binary words[END_REF][START_REF] Shallit | Simultaneous avoidance of large squares and fractional powers in infinite binary words[END_REF]). In this paper we consider instead the existence of infinite cubefree binary words with many distinct squares.

Most known constructions of infinite cubefree words involve the iteration of a morphism. In the early 80's, Berstel [START_REF] Berstel | Mots sans carré et morphismes itérés[END_REF] revitalized the study of the construction of words avoiding repetitions by the iteration of morphisms. Words constructed in this manner are often refered to as infinite D0L words. Ehrenfeucht and Rozenberg [START_REF] Ehrenfeucht | On the subword complexity of square-free DOL languages[END_REF][START_REF] Ehrenfeucht | On the subword complexity of m-free DOL languages[END_REF][START_REF] Ehrenfeucht | On the size of the alphabet and the subword complexity of squarefree DOL languages[END_REF] proved several results concerning the factor complexity of infinite D0L words. They showed that any squarefree or cubefree D0L word has O(n log n) factors of length n. Thus, an infinite cubefree D0L word cannot have many distinct square factors. By constrast, we show here how to construct infinite cubefree binary words containing exponentially many distinct squares of length n.

Other work related to the problems considered here include [START_REF] Aberkane | There exist binary circular 5/2 + power free words of every length[END_REF][START_REF] Currie | Infinite words containing squares at every position[END_REF][START_REF] Currie | Binary words containing infinitely many overlaps[END_REF]. Let µ denote the Thue-Morse morphism: i.e., the morphism that maps 0 → 01 and 1 → 10. The Thue-Morse word is the infinite word t = 011010011001011010010110 • • • † The first author is supported by an NSERC Discovery Grant. ‡ The second author is supported by an NSERC Postdoctoral Fellowship.

1365-8050 c 2010 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France obtained by iteratively applying µ to the word 0. The Thue-Morse word is well-known to be overlap-free, and hence, a fortiori, cubefree [START_REF] Thue | Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen[END_REF]. The squares occurring in the Thue-Morse word were characterized by Pansiot [START_REF] Pansiot | The Morse sequence and iterated morphisms[END_REF] and Brlek [START_REF] Brlek | Enumeration of factors in the Thue-Morse word[END_REF] as follows. Define sets A = {00, 11, 010010, 101101} and

A = k≥0 µ k (A).
The set A is the set of squares appearing in the Thue-Morse word.

Shelton and Soni [START_REF] Shelton | Chains and fixing blocks in irreducible sequences[END_REF] characterized the overlap-free squares (the result is also attributed to Thue by Berstel [START_REF] Berstel | Axel Thue's work on repetitions in words[END_REF]), as being the conjugates of the words in A. (A conjugate of x is a word y such that x = uv and y = vu for some u, v.) Currie and Rampersad [START_REF] Currie | Infinite words containing squares at every position[END_REF] showed that the conjugates of the words in A are also precisely the 7/3-power-free squares. Thus, there are only 7/3-power-free squares of length 2n when n is a power of 2, or 3 times a power of 2. By contrast, we show that there are cubefree binary squares of length 2n for every positive integer n. We use this result to construct infinite cubefree binary words containing exponentially many distinct squares.

Main results

The main results of this paper are the following two theorems.

Theorem 1 Let n be a positive integer. There exists a cubefree binary square of length 2n.

Theorem 2 There exists an infinite cubefree binary word containing exponentially many distinct squares of length n.

We first establish some preliminary results. Proof: Certainly if z is a factor of yy it occurs twice in yyy. If z is a factor of yyy but not of yy, then z must span the central y of yyy and a bit more on both ends, giving z a length of p + 2 or more. 2

Theorem 6 Let x be a factor of the Thue-Morse word of the form x = 1001x = x 1001. Then the word x0x0 is cubefree.

Remark 1 Word 01010 occurs exactly once in x0x0. (Note that this word is an overlap, and hence not a factor of the Thue-Morse word.)

Proof of Theorem 6: Suppose yyy is a cube in x0x0 with |y| = p > 0.

Case 1: Period p ≥ 4.

By Lemma 5 and Remark 1, word 01010 is not a factor of yyy. We have two possibilities:

(a) Cube yyy is a factor of x 100101. This is impossible by Lemma 4, since x 1001 is overlapfree, |01| = 2, and p ≥ 4 > 2.

(b) Cube yyy is a factor of 101001x 0. This is again impossible by Lemma 4, since 1001x is overlap-free.

Case 2: Period p ≤ 3.

If 01010 is a factor of yyy, then one of 001010 and 010100 is a factor. However, neither of these has period 1, 2 or 3; this is impossible. We conclude that 01010 is not a factor of yyy. This gives a similar case breakdown as in Case 1.

(a) Cube yyy is a factor of x 100101.

(i) Cube yyy is a suffix of x 100101. In this case, p ≤ 2 by Lemma 4, since x 1001 is overlap-free. However, the longest suffix of x 100101 of period 1 or 2 is 0101, which is cubefree. (ii) Cube yyy is a suffix of x 10010. This forces p = 1, which is impossible. Proof of Theorem 7: Suppose yyy is a cube in x101100x101100 with |y| = p > 0.

Case 1: Period p ≥ 4. By Lemma 5 and Remark 2, word 00100 is not a factor of yyy. We have two possibilities:

(a) Cube yyy is a factor of x10110010. Word x10110010 contains 11011 as a factor exactly once. By Lemma 5 and Remark 2, there are two possibilities:

(i) Cube yyy is contained in x101.
In this case, p ≤ 3 by Lemma 4, since x is overlap-free. This is a contradiction.

(ii) Cube yyy is contained in 10110010. This is clearly impossible. (b) Cube yyy is a factor of 0x101100.

Again, word 0x101100 contains 11011 as a factor exactly once. Therefore, either yyy is contained in 101100 or in 0x101. The first alternative evidently is impossible, while the second is ruled out by Lemma 4.

Case 2: Period p ≤ 3.

If 00100 is a factor of yyy, then we must have p = 3, since 00100 does not have period 1 or 2. However, in x101100x101100, the maximal factor of period 3 containing 00100 is 1001001, which is not a cube. We conclude that 00100 is not a factor of yyy. This gives a similar case breakdown to Case 1:

(a) Cube yyy is a factor of x10110010. By Lemma 4 the word x10 must be cubefree. Therefore, yyy must be a suffix of one of these words:

w 8 = x 100110110010 w 7 = x 10011011001 w 6 = x 1001101100 w 5 = x 100110110 w 4 = x 10011011 w 3 = x 1001101
None of the w n ends in a cube of period 1, 2 or 3. (In the case of words w 4 , w 3 , the longest suffixes of period 3 have lengths 6 and 5 respectively.) It follows that yyy is not a suffix of any of the w n , and this case does not occur. (b) Cube yyy is a factor of 0x101100.

Since |yyy| = 3p ≤ 9 ≤ |0x|, yyy is a factor of 0x or of x101100. The first possibility was ruled out in the proof of Theorem 6, and the second in Case 2a. 2

Theorems 6 and 7 together establish Theorem 1. Next we show that the number of cubefree binary squares of length n grows exponentially.

Proposition 8 There exist exponentially many cubefree binary squares of length n.

Proof: Let m be a positive integer and let xx be a cubefree binary square of length 2m over {0, 1}. Suppose that 0 occurs at least as often as 1 in x. Construct a new cubefree square yy over {0, 1, 2}, where y is obtained from x by arbitrarily replacing some of the 0's in x by 2's. There are at least 2 m/2 such squares yy of length 2m.

Let h be the morphism

0 → 001011 1 → 001101 2 → 011001.
Brandenburg [START_REF] Brandenburg | Uniformly growing kth power-free homomorphisms[END_REF]Theorem 6] showed that h maps cubefree words to cubefree words. Moreover, since h is uniform and injective, the set of words h(yy) consists of at least 2 m/2 cubefree squares of length 12m.

Asymptotically, we thus have exponentially many cubefree binary squares of length n, as required. 2

We now prove Theorem 2.

Proof of Theorem 2: In the proof of Proposition 8 we showed that there are at least 2 m/2 cubefree binary squares of length 12m for every positive integer m. Let S therefore be any set of cubefree squares over {0, 1} where S contains at least 2 m/2 words of length 12m for every positive integer m. Let x = x 1 x 2 • • • be any infinite cubefree binary word over {2, 3}. Construct a word

w = x 1 S 1 x 2 S 2 • • • ,
where the set of S i 's is equal to the set S, so that w is cubefree and contains exponentially many distinct squares of length n. Let g be the morphism

0 → 001001101 1 → 001010011 2 → 001101011 3 → 011001011.
Brandenburg [START_REF] Brandenburg | Uniformly growing kth power-free homomorphisms[END_REF]Theorem 6] showed that g maps cubefree words to cubefree words. Thus, g(w) is cubefree and, by the uniformity and injectivity of g, contains exponentially many distinct squares of length n. 2

Note that Theorem 2 implies that existence of an infinite cubefree binary word with exponential factor complexity-i.e., with exponentially many factors of length n. Similarly, one can easily construct an infinite squarefree word over {0, 1, 2} with exponential factor complexity.

Proposition 9 There exists an infinite squarefree word over {0, 1, 2} with exponential factor complexity.

Proof: Let w be any infinite squarefree word over {0, 1, 2} and let x be any infinite word over {3, 4} with 2 n factors of length n for every positive n. Let y be the word obtained by forming the perfect shuffle of w and x: that is, if w = w 0 w 1 w 2 • • • and x = x 0 x 1 x 2 • • • , then define y = w 0 x 0 w 1 x 1 w 2 x 2 • • • . Clearly, y is a squarefree word with exponential factor complexity. Let f be the morphism

0 → 010201202101210212 1 → 010201202102010212 2 → 010201202120121012 3 → 010201210201021012 4 → 010201210212021012.
Brandenburg [START_REF] Brandenburg | Uniformly growing kth power-free homomorphisms[END_REF]Theorem 4] showed that f maps squarefree words to squarefree words. The uniformity and injectivity of f implies that f (y) is a squarefree word with exponential factor complexity, as required.

2

Lemma 3 2 Lemma 4 2 Lemma 5

 32425 The Thue-Morse word contains a factor of the form x = 1001x = x 1001 of every positive even length n = 2, 6.Proof: Aberkane and Currie [1,Lemma 4] proved that for every integer m ≥ 6, the Thue-Morse word contains a factor of length m of the form 10y10. Then the Thue-Morse word also contains the factor µ(10y10) = 1001µ(y)1001, which has length 2m. Finally, we observe that 10011001 and 1001101001 are factors of the Thue-Morse word of lengths 8 and 10 respectively. If y is overlap-free and ayb is a cube of period p, then p ≤ |ab|.Proof: Otherwise deleting a and b removes less than a full period from ayb, leaving an overlap. If z is a factor of yyy where |y| = p and |z| ≤ p + 1, then there are two occurrences of z in yyy.

( b )

 b Cube yyy is a factor of 101001x 0.

( i ) 2 Theorem 7 Remark 2

 i272 Cube yyy is a prefix of 101001x 0 or of 01001x 0. If x is the empty word, then x0x0 = 1001010010 is clearly cubefree, so let us assume that |x | ≥ 4. Since |yyy| = 3p ≤ 9 ≤ |01001x |, yyy is a factor of 101001x . This is symmetrical to Case 2a. (ii) Cube yyy is a factor of 1001x 0 = x0. This is impossible by Case 2a. Let x be a factor of the Thue-Morse word of the form x = 1001x = x 1001. Then the word x101100x101100 is cubefree. Word 00100 occurs exactly once in x101100x101100. Word 11011 occurs exactly twice.


Yvonne Anne Pignolet

Stefan Schmid
email: stefan@net.t-labs.tu-berlin.dewattenhofer@tik.ee.ethz.ch

Roger Wattenhofer

Tight Bounds for Delay-Sensitive Aggregation †

Keywords: Competitive Analysis, Wireless Sensor Networks, Distributed Algorithms, Aggregation

This article studies the fundamental trade-off between delay and communication cost in networks. We consider an online optimization problem where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about the changes of their states and to use as few transmissions as possible. We derive an upper bound on the competitive ratio of O(min(h, c)) where h is the tree's height, and c is the transmission cost per edge. Moreover, we prove that this upper bound is tight in the sense that any oblivious algorithm has a ratio of at least Ω(min(h, c)). For chain networks, we prove a tight competitive ratio of Θ(min( √ h, c)). Furthermore, we introduce a model for value-sensitive aggregation, where the cost depends on the number of transmissions and the error at the root.

Introduction

The analysis of distributed algorithms often revolves around time and message complexity. On the one hand, we want our distributed algorithms to be fast, on the other hand, communication should be minimized. Problems often ask to optimize one of the two-and treat the other only as a secondary target. However, there are situations where time and message complexity are equally important.

In this article, we study such a case known as distributed aggregation (a.k.a. multicast aggregation). Nodes of a large distributed network may sense potentially interesting data which they are to report to a central authority (sink). Not only should the data make its way fast through the network such that information is not unnecessarily delayed; but also, since message transmission is costly, one may reduce the number of transmissions by aggregating messages along the way. In other words, nodes may wait for further packets before forwarding them in order to decrease the number of transmission at the expense of a later arrival of the information at the sink. This problem has many applications. In the past it was mostly studied in contexts such as control message aggregation. In the heyday of wireless networking the first application that comes to mind is perhaps sensor networking. Due to energy constraints, it is necessary to minimize the number of transmissions. At the same time, it is desirable to aim at minimizing the time until the sink is informed about changes of measured values.

We assume that the communication network of the nodes forms a pre-computed directed spanning tree on which information about events is passed to the root node (the sink). Data arrives at the nodes in an online (worst-case) fashion. The main challenge is to decide at what points in time the data should be forwarded to a parent in the tree.

Related Work

The trade-off between delay and communication cost appears in various contexts, and plays a role in the design of algorithms for wireless sensor networks, for Internet transfer protocols, and also appears in organization theory. This section gives a brief overview of related work on this topic.

A basic problem in the design of Internet transfer protocols such as the TCP protocol concerns the acknowledgments (ACKs) which have to be sent by a receiver in order to inform the sender about the successful reception of packets: In many protocols, a delay algorithm is employed to acknowledge multiple ACK packets with a single message or to piggy-back the ACK on outgoing data segments [START_REF] Stevens | TCP/IP Illustrated[END_REF]. The main objective of these algorithms is to save bandwidth (and other overhead at the sender and receiver) while still guaranteeing small delays. The problem of aggregating ACKs in this manner is also known as the TCP acknowledgment problem, which was proved to be 2-competitive [START_REF] Daniel | TCP Dynamic Acknowledgment Delay: Theory and Practice[END_REF]. Karlin et al. [START_REF] Karlin | Dynamic TCP Acknowledgement and Other Stories About e/(e -1)[END_REF] pointed out interesting relationships of the single-link acknowledgment problem to other problems such as ski-rental, and gave an optimal, e/(e -1)-competitive randomized online algorithm (where e = 2, 7182... is the Euler number).

There are many variations of the theme, e.g., Albers et al. [START_REF] Albers | Dynamic TCP Acknowledgement: Penalizing Long Delays[END_REF] seek to minimize the number of acknowledgments sent plus the maximum delay incurred for any of these packets. They propose a π 2 /6competitive deterministic algorithm for the single link (where π = 3.1415...), which is also a lower bound for any deterministic online algorithm. Frederiksen et al. [START_REF] Frederiksen | Packet Bundling[END_REF] consider deterministic and randomized algorithms for bundling packets in a single-link network. They observe that because of physical network properties, a certain minimum amount of time must elapse in-between the transmission of two packets; the trade-off is investigated that on the one hand waiting delays the transmission of the current data, and on the other hand sending immediately may delay the transmission of the next data to become available even more.

There is also much literature on aggregation in sensor networks [KEW02, KLS08, SBAS04, SO04, vRW04, YF05, YKP04]. E.g., Becchetti et al. [BKMS + 06] studied online and offline algorithms for scenarios where fixed deadlines must be met. They show that the offline version of the problem is strongly NP-hard and provide a 2-approximation algorithm. More complexity results for settings with fixed deadlines have been derived in [START_REF] Nonner | Latency Constrained Aggregation in Chain Networks Admits a PTAS[END_REF]. Korteweg et al. [KMSSV09] address a similar problem following a bicriterion approach which considers time and communication as two independent optimization problems: A (B, A)-bicriterion problem minimizes objective A under a budget on objective B. Inter alia, the authors prove that if r is the ratio between the maximum and the minimum delay allowed, then the competitive ratio of their algorithm is (2h λ , 2h 1-λ log r) for any λ in (0, 1].

The paper closest to our work is by Khanna et al. [START_REF] Khanna | Control Message Aggregation in Group Communication Protocols[END_REF] which investigates the task of centralized and decentralized online control message aggregation on weighted tree topologies. In particular, [START_REF] Khanna | Control Message Aggregation in Group Communication Protocols[END_REF] presents a O(h log α)-competitive distributed algorithm, where h is the tree's height, and α is the sum of the weights of the tree's edges. Moreover, the authors show that any oblivious distributed online algorithm has a competitive ratio of at least Ω( √ h) (an oblivious algorithm bases the decisions at each node solely upon the static local information available at the node).

In this article, we study the same algorithm and we give a new analysis for scenarios where the communication cost is c on all links, resulting in a better upper bound of O(min (h, c)). We also derive a new generalized lower bound for edge cost which is different from h, and show that for any oblivious aggregation algorithm, the competitive ratio is at least Ω(min(h, c)). Moreover, by taking into account many intrinsic properties of the algorithm, we show that for chain graphs an upper bound of O(min( √ h, c)) holds. This is asymptotically tight. Brito et al. [START_REF] Brito | Competitive Analysis of Organization Networks or Multicast Acknowledgement: How Much to Wait?[END_REF] extended the work of Khanna et al. by proving general upper and lower bounds for the asynchronous and the centralized ACK aggregation problem. Interestingly, the asynchronous model yields higher lower bounds in the distributed case than the synchronous ("slotted") model, e.g., the lower bound for the chain network is Ω(h) in the distributed asynchronous model, a factor of √ h greater than the bounds in the synchronous model. Finally, our value-sensitive aggregation model is reminiscent of the recent "online tracking" work by Yi and Zhang [START_REF] Yi | Multi-dimensional Online Tracking[END_REF]. The authors study a 1-lookahead scenario where Alice outputs a function f : Z + → Z d , and Bob, knowing all values at t ≤ t now needs to guess f (t) in an online fashion. Different scenarios are examined, and competitive strategies are presented that result in small errors only and save on communication cost. Our model differs from [START_REF] Yi | Multi-dimensional Online Tracking[END_REF] as it describes a 0-lookahead model and as in their model, nodes are forced to send updates if the measured value differs sufficiently from the value stored at the root.

Model

The network to be considered is modeled by a rooted tree T = (V, E) of height h with root r ∈ V and n = |V | nodes. Every node u except for the root r (the sink) has a parent node v, i.e., an edge (u, v) ∈ E. The cost of transmitting a message over an edge is c ≥ 1; we assume that nodes know the value c. Besides general trees, we will also study chain networks (sometimes also referred to as linked lists networks or linear arrays in literature) where each node has exactly two neighbors except for the root and the leaf node which have 1 neighbor.

We assume that events occur at the leaf nodes L ⊂ V (e.g., a control message arriving at a node, or a sensor node detecting an environmental change). We will refer to the information about the occurrence of a single event as an event packet. Leaf l creates an event packet p for every event that happens at l.

Eventually, all event packets have to be forwarded to the root. Instead of sending each packet p ∈ P individually to a node's parent after the event took place, nodes can retain packets and send a message m consisting of one or more packets together later, thus saving on communication cost as we have to pay for a link only once per message (rather than per event). Messages can be merged iteratively with other messages on their way to the root.

We consider a synchronous model where time is divided into time slots. In each slot, an arbitrary number of events can arrive at each node. For an event packet p, t l (p) denotes the time slot its corresponding event occurred at a node and t r (p) the time when it reaches the root. For each time slot an event waits at a node, we add one unit to the delay cost, i.e., the delay cost dc (p) the event accumulates until reaching the root is dc (p) = t r (p) -t l (p).

Each message can only be forwarded one hop per time slot, i.e., a message always has to wait one time slot at a node before being transmitted to the next node. Thus, the delay accumulated by an event is at least h l , where h l denotes the length of the path from the respective leaf l to the root. The total delay cost of all events accumulated up to time slot T is hence

dc T = p∈P,tr(p)≤T dc (p) + p∈P,tr(p)>T (T -t l (p)).
Nodes can aggregate as many event packets as needed. At each time step t, a node may aggregate awaiting event packets and forward the resulting message to its parent. The cost of sending a message is c per edge no matter how many event packets it contains. Consequently, the total communication cost is the sum of the edge cost of all message transmissions. More formally, let S t be the set of nodes sending out a message in time slot t, then the total communication cost cc T up to time slot T is cc T = T t=1 |S t |. The total cost up to time T is the sum of both the delay and the communication cost,

cost T = dc T + cc T .
Observe that the edge cost c allows us to weight delay and communication cost: A larger c implies that communication cost become relatively more important compared to the delay cost. Note that we neglect the energy consumption in idle listening mode and consider the nodes' transmission cost only. We believe that this is justified for networks where listening nodes have their radios turned off most of the time and only check for data transfers at the very beginning of each time slot.

Nodes do not know the future arrival time of events, and hence have to make the decisions on when to send messages online. We are in the realm of competitive analysis (see, e.g., the work by Sleator and Tarjan [START_REF] Daniel | Amortized Efficiency of List Update and Paging Rules[END_REF], or the introductory book by Borodin [START_REF] Borodin | Online Computation and Competitive Analysis[END_REF]) and define the (strict) competitive ratio ρ achieved by an online algorithm ALG as the delay and communication cost of ALG divided by the total cost of an optimal offline algorithm OPT that knows the event arrival sequences a priori. Definition 1.1 (ρ-competitiveness) An online algorithm ALG is (strictly) ρ-competitive compared to an optimal offline algorithm OPT if for all input sequences S, i.e., all possible event arrival sequences,

cost ALG (S) ≤ ρ • cost OPT (S).
The goal of an online algorithm designer is hence to devise algorithms minimizing ρ, as a small ρ describes the guaranteed worst-case quality of an algorithm.

We focus on oblivious online algorithms.

Definition 1.2 (Oblivious Algorithms) A distributed online algorithm ALG is called oblivious if the decisions by each node v ∈ V whether to transmit a message solely depends on the number of events currently stored at node v and on the arrival times of the corresponding messages at node v.

In particular, Definition 1.2 implies that the decisions of a node v do not depend on packets forwarded by v earlier or on v's location in the aggregation network. Being oblivious is a desirable property of distributed algorithms, since non-oblivious algorithms need dynamic updating mechanisms-a costly operation. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 root v 1 v 2 v 3 events at node v 1 v 2 t = 1 1 0 t = 2 1 2 delay at node v 1 v 2 v 3 t = 1 1 0 0 t = 2 3 2 0 t = 3 0 4 2 t = 4 0 0 6 t = 5 0 0 0
Fig. 1: Example execution of KN R where the transmission cost c is 3.

Our Contribution

We prove that the simple algorithm introduced in [KNR02] achieves a competitive ratio of O(min(h, c)) where h is the tree's height, and c is the transmission cost per edge. This improves an existing upper bound of O(h log(cn)), where n is the network size. We also demonstrate that this upper bound is tight in the sense that there exist problem instances where any oblivious algorithm has a ratio of at least Ω(min(h, c)). Earlier work proved a lower bound of Ω( √ h) on a chain network. Therefore, we examine this topology more closely and show that chain networks are inherently simpler than general trees by giving a competitive ratio of Θ(min( √ h, c)) for oblivious algorithms. In the last part of this article, we present an event aggregation model which takes into account that nodes often have non-binary data to aggregate and greater differences between values need to be reported to the root faster than small differences. We present a model comprising this additional constraint as well as an oblivious algorithm achieving a competitive ratio of O(c/ ) on a one-link network, where is the minimum difference between two values. We also describe an optimal offline algorithm (requiring polynomial time) for this model.

Oblivious Online Algorithm

This section describes and analyzes the deterministic online algorithm KN R presented in [START_REF] Daniel | TCP Dynamic Acknowledgment Delay: Theory and Practice[END_REF][START_REF] Khanna | Control Message Aggregation in Group Communication Protocols[END_REF]. The algorithm is oblivious in the sense that decisions are reached independently of the distance to the root (cf Definition 1.2). Essentially, the event aggregation algorithm KN R seeks to balance the total delay cost and the total communication cost. In order to do so, it aggregates information about multiple events into one message until the forwarding condition is satisfied. Whenever a new event occurs or a message arrives, it is merged with the message waiting for transmission at the node.

For a message m at node v, we define delay v (m, t), denoting the delay associated with message m currently stored at node v at time t. Informally, it is the sum of the accumulated delay cost at node v of all the event packets the message m contains. In every time step a message remains at a node, delay v (m, t) is increased by the number of packets in the message. If a message arrives at a node where another message is already waiting to be forwarded, the two messages are merged. More formally, let a message m be a set of merged messages {m 1 , . . . , m k }, where message m i consists of |m i | packets and arrived at the current node in time slot t i . The delay of message m at node v at time t is defined by

delay v (m, t) := k i=1 |m i |(t -t i ).
When executing algorithm KN R, a node v forwards a message m to its parent as soon as the current accumulated delay exceeds the transmission cost:

delay v (m, t) ≥ c. 1 2 3 4 … t i t i+1 t i+2 time OPT OPT AGG AGG AGG AGG AGG AGG
Fig. 2: Illustration of a sequence of event arrivals at a leaf and the corresponding forwarding actions of the online algorithm KN R for c = 4. In addition, the time slots where the optimal offline algorithm forwards its messages are marked as well. Note that we cannot verify in this limited view of a leaf node how much better OPT 's decisions are because of our lack of knowledge on the situation at the other nodes.

We demonstrate the execution of KN R on a simple example. Consider the tree and the event arrival sequence in Figure 1. There are two events occurring at leaf node v 1 , one in time slot t = 1, one at time t = 2. Node v 2 receives two packets at t = 2. The transmission cost is set to c = 3. For this input sequence, node v 1 sends its two packets after time t = 2 and node v 2 after time t = 3, i.e., as soon as the accumulated delay reaches or exceeds c = 3. Node v 3 incurs a delay of two after the message from v 1 arrives. In the next time slot, v 3 's delay cost increases to 6, as the message from v 2 arrives with two additional packets, so there are four messages at v 3 now.

Tight Bound for Trees

Upper Bound

We establish a new upper bound of O(min(h, c)) on the competitive ratio of KN R by a surprisingly simple analysis. Instead of calculating the delay and the communication cost the event packets accumulate, we focus on the messages KN R and OPT send. We proceed as follows. First, we investigate the competitiveness of KN R for a single link network, then tackle the chain network, and finally generalize our analysis to tree topologies. Theorem 3.1 On arbitrary trees, the competitive ratio of KN R is at most

ρ = cost KN R cost OPT ∈ O(min (h, c)).
Proof: We begin by analyzing one path from a leaf l to the root. Given a sequence of event arrivals at the leaf, we can compute when KN R sends messages to the leaf's parent node. We study the cost accumulated by these messages in groups of three messages. Then our results are generalized to trees.

Lemma 3.2 For the events occurring at a given leaf l, the competitive ratio is at most O(min (h l , c)).

Proof: Given a sequence of event arrivals at the leaf, we can compute when KN R sends messages to the leaf's parent node. We define m A i to be the i th message that leaf node l, located at depth h l , sends to its parent. Let t 0 be the first time slot, and the time slot when message m A i is forwarded towards the root by l is denoted by t i . Let the total number of messages that leaf l transmits be M A l . If such a message m A i contains less than c packets it incurs a transmission cost of c and a delay cost of less than 2c per hop towards the root. If a message consists of more than c packets, the delay cost per hop is bounded by the number of packets. Thus, the total cost for KN R amounts to at most h l (c + max(2c, |m A i |)) for m A i . In order to determine the minimum cost an offline algorithm accumulates, we divide the time into intervals of three message transmissions. More precisely, we consider time periods [t j , t j+3 ], where j mod 3 = 0. There are two possibilities for algorithm OPT : Either it sends one or more messages in the period [t j , t j+3 ] as well, yielding at least a transmission cost of c, or the delay accumulated by these packets is at least c. Either way, the cost accumulated by OPT at leaf l for these packets is at least c. In addition, the delay cost accumulating until the packets arrive at the root is at least

(h l -1)(|m A j | + |m A j+1 | + |m A j+2 |)
, since every packet in m A j , m A j+1 and m A j+2 incurs a delay cost of at least one for each hop towards the root. Thus, OPT 's total cost for a period [t j , t j+3 ] is at least

c + (h l -1)(|m A j | + |m A j+1 | + |m A j+2 |).
Unless M A l mod 3 = 0, we cannot consider all messages in groups of three. If there are one or two last messages that do not belong to such a group, the respective cost of OPT for the period

[t 3 M A l /3 , t M A l ] is at least c + (h l -1)|m M A l | or c + (h l -1)(|m M A l | + |m M A l -1 |).
This implies that for any given sequence of event arrivals at a leaf the competitive ratio is

ρ = cost KN R cost OPT ≤ M A l j=1 h l (c + max(2c, |m A j |)) c M A l /3 + M A l j=1 h l |m A j | ≤ 3M A l h l c + M A l j=1 h l |m A j | cM A l /3 + M A l j=1 h l |m A j | < 3M A l h l c M A l (c/3 + h l ) + 1 ∈ O (min (h l , c)) .
2

Observe that we make no assumptions on the behavior of the optimal algorithm in Lemma 3.2. Moreover, we charge the optimal algorithm OPT only for the transmissions over the edges between the leaves and their neighbors when bounding OPT 's communication cost, i.e., we basically exempt the optimal algorithm from paying for any other transmission. Furthermore, we ignore the cost KN R could potentially save by merging messages on their way to the root: We assign the highest possible delay and communication cost to every message of KN R. These properties allow us to extend Lemma 3.2 to trees without modification: More precisely, if we consider the longest path in the tree the statement holds for general trees as well.

root v 1 v 2 v 3 ... v n/2-1 v n/2
Fig. 3: Lower bound topology.

Lower Bound

We conclude our investigations of the tree network with a lower bound stating that KN R is asymptotically optimal compared to any oblivious algorithm (Definition 1.2). For oblivious algorithms, it holds that the wait time w only depends on the packet arrival time of the packets currently stored by a given node.

Theorem 3.3 On trees, any oblivious deterministic online algorithm ALG has a competitive ratio

ρ = cost ALG cost OPT ∈ Ω(min(h, c)).
Proof: Consider the tree topology depicted in Figure 3 which consists of a chain network of n/2 + 1 nodes, where all nodes except for the two last ones have an additional neighbor (n even). The leaf nodes are referred to by v 1 , ..., v n/2 . We compute the minimum delay and communication cost any oblivious online algorithm ALG will accrue for input sequence where all leaves simultaneously get one packet. Since ALG is oblivious, according to Definition 1.2, each leaf node v i will send the packet to its parent after waiting for w time slots, where the packet arrives at time w + 1. (The value of w ≥ 0 depends on the chosen algorithm; observe that w is the same for all nodes, because we assume ALG to be oblivious.) From there, the packets leave at time 2w + 2. This process is repeated until all packets reach the root. Generally, the packet of leaf node v i will arrive at a node at distance j from v i at time j + jw, and will stay there for w time slots. Observe that the packets of two nodes v i-1 and v i are never merged into one message. Thus, ALG has communication cost in the order of Θ h 2 c and delay cost in the order of Θ h 2 .

The optimal algorithm OPT has to send at least one message over each edge, resulting in a communication cost of Θ (ch). The minimum delay cost until all packets reach the root is Θ h 2 . If all the packets are merged into one message on their way to the root, the delay and communication cost is in this order of magnitude. Thus we have the following (asymptotic) competitive ratio:

ρ = cost ALG cost OPT ∈ Ω h 2 + h 2 c 2hc + h 2 .

2

This result implies that KN R is asymptotically optimal in the sense that there exists no oblivious online algorithm achieving a better performance.

Discussion

Note that the above analysis for upper and lower bounds carries over to the model where events can appear at any node, not only at the leaves: The case where events occur at inner nodes can be reduced to a problem instance where events only occur at leaves by simply creating a new tree with additional leaves attached to any node where events occur; we have to map the arrival time slots to earlier time slots, ensuring that they arrive at the inner nodes at the correct time.

Theorem 3.1 can be compared to the results obtained in [START_REF] Khanna | Control Message Aggregation in Group Communication Protocols[END_REF]. There, an upper bound of O (h log α) is derived for the competitive ratio of KN R, where α is the total communication cost (sum of edge weights) of the tree. If all edges have a weight c, this translates into O (h log (nc)), which is O h 2 log c in balanced binary trees. In this case, the analysis presented above is better by a factor of Θ (h log c) if h < c. In other networks, for instance, on chain topologies, the gap between the two bounds narrows, although there always remains a factor in the order of Ω(log(max(h, c)): Let us only take the edges on the longest path into account for the upper bound of [START_REF] Khanna | Control Message Aggregation in Group Communication Protocols[END_REF]. Thus the bound reduces to O(h log(hc)). If c > h this is O(h log c) whereas the bound presented here is O(h). If c < h the bound from [START_REF] Khanna | Control Message Aggregation in Group Communication Protocols[END_REF] gives O(h log h) and our analysis results in O(c). Technically the difference between our approach and the approach in [START_REF] Khanna | Control Message Aggregation in Group Communication Protocols[END_REF] is the way we sum up the delay cost of the algorithms. In [START_REF] Khanna | Control Message Aggregation in Group Communication Protocols[END_REF], the sum of the delay cost per packet for KN R is expressed in terms of the delay cost per packet of the optimal offline algorithm: By a potential function argument, it is shown that the number of packets that reach the root later than in the optimal case decreases quickly over time. This implies that the total delay cost of the online algorithm cannot be much larger than the total delay cost of the offline algorithm. In contrast, in our approach we consider the absolute cost the online and offline algorithms accumulate. Like in [START_REF] Khanna | Control Message Aggregation in Group Communication Protocols[END_REF], there is no need to study merge behavior explicitly.

Tight Bound for Chains

Upper Bound

The previous section has already discussed the implications of our tree analysis on the performance of KN R on chain networks. In the following, we go one step further and take a closer look at chains. We show by a more detailed analysis that the bound derived there can be improved. In particular, we leverage the fact that the algorithm can merge messages and forward them together, i.e., save on transmission cost. Moreover, a merged message moves faster towards the root since it now contains more packets and reaches the forwarding threshold in fewer time slots than the two separate messages consisting of fewer packets. Concretely, we prove that on the chain topology, KN R is O(min √ h, c)-competitive, and that no oblivious algorithm can be less than Ω(min(c, √ h))-competitive.

Theorem 4.1 In chain graphs, the competitive ratio of KN R is

ρ = cost KN R cost OPT ∈ O min √ h, c .
Proof: Since a chain is a tree, we already know that O(min(c, h)) and hence O(c) is an upper bound on the competitive ratio due to Theorem 3.1. It remains to prove that O( √ h) is an upper bound on the competitive ratio for chain networks. We use the following lemmata repeatedly. Lemma 4.2 When executing KN R, a message consisting of n i packets that arrive at the leaf at the same time reaches the node at distance l from the leaf after l c/n i time slots if the message does not merge with any other message.

Proof: Let t j denote the time the message spends at depth h j , i.e., at the j th node of its path to the root. Since KN R is oblivious and no messages are merged, t j = c/n i is the same for every node of the chain. Thus the number of time slots the message spends on a path of length l is l-1 j=0 t j = l c/n i . 2 Lemma 4.3 If KN R does not merge any messages then there are at least

h c n i -(h -1) c n i+1
time slots between the arrival of the packets of m A i and the arrival of the packets of m A i+1 at the leaf node, if m A i+1 contains more packets than m A i .

Proof: To ensure that m A i reaches the root separately even though it is followed by a larger message, m A i has to have arrived at the root before m A i+1 arrives at the node in depth 1. By Lemma 4.2 we know that m A i reaches the root h c/n i time slots after its arrival at the leaf. If m A i+1 arrives at the leaf δ i time slots after the departure of m A i then it reaches the node in distance 1 to the root(h -1) c/n i+1 time slots later. Hence we can derive the inequality h c/n i < δ i + (h -1) c/n i+1 and the claim follows.

2

Since a smaller message moves at a lower speed, a message m i+1 containing n i+1 packets can never catch up with a message m i with n i+1 or more packets, even if there is only one time slot between their departure and arrival.

We start analyzing input sequences where KN R does not merge any messages at inner nodes. We then show that merge operations cannot deteriorate the competitive ratio.

Let m A i denote the i th message of KN R and let n i be the number of packets contained in message m A i . Without loss of generality, we assume that for each message m A i of KN R, all n i packets arrive simultaneously, since an optimal offline algorithm OPT would clearly incur the same or higher delay cost if packets arrived dispersed over time. We will be referring to this assumption as Assumption 1. Lemma 4.4 Given a sequence of packet arrivals where KN R does not merge any messages, the ratio between the cost of KN R and the cost of OPT is maximized if the number of time slots between the arrival of the packets of m A i and the packets of

m A i+1 is h c n i -(h -1) c n i+1
.

Proof: Due to Lemma 4.3, the minimum number of time slots between the arrival of the packets of

m A i and m A i+1 is h c/n i -(h -1) c/n i+1 .
For KN R, the delay cost and the communication cost is neither reduced nor increased if there are more time slots in-between the arrivals. If OPT merges two or messages of KN R, the delay cost is increased if there are more time slots between the arrival of packets of consecutive messages. Hence, the claim follows, as the competitive ratio is maximized when OPT 's cost is minimized.

2

Thus we can assume without loss of generality that there are exactly h c/n i -(h -1) c/n i+1 time slots between the arrival of consecutive messages thanks to Lemma 4.4. We will be referring to this assumption as Assumption 2. Lemma 4.5 For sequences where KN R does not merge any messages, the competitive ratio of KN R is O( √ h) on chain graphs.

Proof: We pick a transmission of the optimal offline algorithm OPT and compare the cost accumulated for the packets within this message to the cost the online algorithm KN R incurs for the same packets. We show that the competitive ratio for each such transmission is O( √ h) by proving an upper bound on the cost for the online algorithm KN R followed by a lower bound on the cost the optimal algorithm accrues.

Let us consider the case where OPT 's message m O consists of packets distributed over z messages m A i by the online algorithm KN R. In other words, we assume that for a certain number of packets, the online algorithm sends messages m A i where i ∈ {1, . . . , z} and OPT sends one message m O . If there are any packets in the first or the last message of KN R that the optimal algorithm OPT does not include in m O , we ignore them when computing the delay and communication cost for OPT . For i = 1 or i = z we set n i to the number of packets that are in m A i and in m O . When sending the z messages individually to the root, KN R incurs a transmission cost of cc KN R = zhc and a delay cost of dc KN R < 2zhc. After having bounded the cost for KN R we now turn to the minimum cost an offline algorithm faces. Clearly, the transmission of m O entails a communication cost of cc OPT = ch for OPT . As a next step we want to determine the minimum delay cost accumulated by the z messages m A i , which are merged into message m O by the optimal algorithm.

We consider two cases: a) the minimum delay cost if the majority of messages is large, i.e., contains more than c/2 packets, and b) the minimum delay cost if the majority of the packets is small, i.e., consists of at most c/2 packets. We show that in both cases the delay cost of the optimal algorithm is Ω(cz 2 ).

a) If more than z/2 messages contain more than c/2 packets, we ignore all other messages and focus on the messages with n i > c/2. Let δ j denote the number of time slots between the arrival of message m A j and the arrival of m A j+1 . Assume there are y messages with n i > c/2. They are responsible for a total delay cost of at least dc OPT > y i=1 n i y j=i δ j . Even when δ j = 1 for all j, this sum amounts to

dc OPT > y i=1 n i y j=i δ j ≥ y i=1 c 2 (y -i) ∈ Ω(y 2 c).
Thus this sum is Ω(z 2 c), because y > z/2. b) If the majority of messages m A i contain at most c/2 packets, we ignore the other messages. For simplicity's sake we let z denote the number of messages with n i ≤ c/2. Let λ i denote the time period between the arrival of the n i packets and the time slot when the corresponding message m A i departs from the leaf. Moreover, let δ i be the time period after the message has departed from the leaf until the next set of n i+1 packets arrives. See Figure 4 for an example.

The total sum of the delay cost OPT accumulates at the leaf for all messages m A i is given by

dc OPT = z-1 i=1 n i z-1 j=i (λ j + δ j ) . m i m i+1 m i+2 λ i λ i+1 δ i δ i+1 δ i-1 time m i m i+1 m i-1
Fig. 4: A sequence of message arrivals and departures for KN R at a leaf. The message m A i is forwarded after δi time slots at the leaf. δi time slots later the next message arrives.

The following two key facts enable us to derive a bound for the delay cost the optimal algorithm incurs by waiting until the packets of all messages m A i have arrived at the leaf:

Fact 1 If the number of packets between two messages differs by a factor of at most two, the time they spend at the leaf differs by the same factor. More formally, if 2n i > n j , j > i then,

λ j = c/n j > c/2n i ≥ λ i /2.
Fact 2 If the difference between the size of two messages is larger than a factor of two, we can apply Lemma 4.3 to compute the minimum number of time slots between their arrival that ensures that a larger message cannot catch up with a smaller message on its path to the root. It holds that if 2n i < n j , j > i then the number of time slots m A j arrives later than m A i is at least

h c n i -(h -1) c n j ≥ h c n i -(h -1) ( c n j + 1) > 2hc -(h -1)(c -2n i ) 2n i > hc 4n i ,
as n i < c/4 due to our assumption that the largest message contains at most c/2 packets and no messages are merged after they leave the leaf node.

We construct a binary vector a where a i = 1 if there exists a message m A j with j > i and 2n i < n j . Using this vector we can rewrite the delay cost dc OPT the optimal algorithm incurs at the leaf.

dc OPT = z-1 i=1 n i z-1 j=i (λ j + δ j ) > z-1 i=1 n i   a i hc 4n i + (1 -a i ) z-1 j=i c 2n i   (1) > z-1 i=1 a i hc 4 + (1 -a i )(z -1 -i)c 2 = c 4 z-1 i=1 (a i (h -2z + 2 + 2i) + 2z -2 -2i) . (2)
In (1), we used Facts 1 and 2 to bound z-1 j=i λ j +δ j . If a i = 1, we apply Fact 2 and the sum is replaced by the number of time slots until the large message responsible for a i = 1 arrives, in the other case, we have a lower bound for λ j due to Fact 1.

If h > z -2 the sum in (2) is minimized if a i = 0 for all messages. In this case it holds that

dc OPT > c 4 z-1 i=1 (2z -2 -2i) = c 4 (z -1)(2z -2 -z) > c 4 (z -2) 2
∈ Ω(cz 2 ).

If h < z -2, then z-1 i=1 a i (h -2z + 2 + 2i
) can be negative. This sum is minimized if the messages with a i = 1 occur first. Let the number of these messages be y. In this case, we have to consider

y i=1 h -2z + 2 + 2i = y(h -2z + 3 + y), which reaches its minimum of -(1/4)(2z -h -3) 2 for y = z -h/2 -3/2. Consequently, dc OPT > c 4 z-1 i=1 (a i (h -2z + 2 + 2i) + 2z -2 -2i) > - c 16 (2z -h -3) 2 + c 4 (z -2) 2 ∈ Ω(cz 2 ).
Hence dc OPT is Ω(cz 2 ) in both cases a) and b); finally:

ρ = cost KN R cost OPT ∈ O zhc cz 2 + ch = O min h z , z = O √ h .
We now investigate what happens if there are fewer time slots between packet arrivals, i.e., situations where merge operations can occur. To this end, we consider a sequence of packet arrivals without merge operations and compare it to the same sequence where the number of time slots between consecutive arrivals is reduced. More precisely, let S = {(n 1 , t 1 ), (n 2 , t 2 ), . . .} denote a sequence of packet arrivals, where (n i , t i ) describes the arrival of n i packets in time slot t i . We compute the difference between the cost accumulated for sequences S = {(n 1 , t 1 ), (n 2 , t 2 ), . . .} without merged messages and S = {(n 1 , t 1 ), (n 2 , t 2 ), . . .}, where for all i > 0 it holds that n i = n i and t i+1 -t i ≥ t i+1 -t i .

Lemma 4.6 Consider a transmission of OPT in the sequence S and assume that KN R merges µ i messages into one message at hop distance i from the leaf. Compared to a sequence S where no messages are merged, KN R can reduce its cost by at least Ω(

µ i • c • (h -i)).
Proof: If the µ i messages are sent to the root separately, the online algorithm pays µ i (h-i)c communication cost for the transmissions between the node at distance i to the root node. By merging theses messages the cost for the transmission amounts to

(h -i)c, consequently the difference is in Ω(µ i • c • (h -i)). 2
Lemma 4.7 Consider a transmission of OPT in the sequence S and assume that KN R merges µ i messages into one message at hop distance i from the leaf. Compared to a sequence S where no messages are merged, OPT can reduce its cost by at most

O(µ i • c • (h -i)).
Proof: Consider the µ i messages that KN R merges at node i. Note that message j of size n j cannot catch up with a message of greater size n j > n i unless it merges with another message first. This implies, that in order to have µ i messages merging at distance i from the leaf, the message size of KN R's messages has to be strictly monotonically increasing.

In the following, let the superscript s identify variables considered in the scenario where KN R does not merge any messages, and the superscript m identify variables in the other scenario. Let λ l + δ l denote the time period between two consecutive arrival time slots of the set of n l and the set of n l+1 packets, where λ l = c/n l is the number of time slots the l th message spends at the leaf δ l is the number of time slots between m A l 's departure and m A l+1 's arrival that ensure that m A l+1 does not catch up (too early) with m A l . For sequences where KN R does not merge any packets, OPT 's delay cost is given by

dc s = µi-1 l=1 µi-1 j=l n l (δ s j + λ j ).
In order to guarantee that consecutive messages are not merged by KN R it holds that δ s l = h c/n l -(h -1) c/n l+1 -c/n l due to Lemma 4.3 and Assumptions 1 and 2. Since n l < n l+1 , we know that δ s l < h( c/n l -c/n l+1 ). Note that this entails that

µi-1 j=l δ s j ≤ h ( c/n l -c/n µi ) .
If we assume the merge operation of µ i messages to happen at depth h -i we can compute a lower bound for the shortened time period between two messages. Observe that in order to ensure that messages do not merge too early, it must hold that δ m l ≥ i c/n l -(i -1) c/n l+1 -c/n l . Due to n l < n l+1 , δ m l ≥ (i -1)( c/n l -c/n l+1 ) and thus µi-1 j=l δ m j ≥ (i -1) ( c/n µi -c/n l ) .

Combining the above, OPT can reduce its delay cost by at most

∆dc OPT = dc s -dc m ≤ µi-1 l=1 n l h c n l - c n µi -n l (i -1) c n l - c n µi ≤ µi-1 l=1 n l (h -i + 1)) c n l - c n µi + 1 = (µ i -1)(h -i + 1)(c + 1).
2 Lemma 4.8 Consider a sequence of packet arrivals on a chain graph satisfying the following conditions: KN R sends some messages individually to the root and performs one merge operation on the other messages. If OPT merges all these messages into one at the leaf then the competitive ratio is O( √ h).

Proof: Let the number of messages KN R sends individually to the root be denoted by ν and the number of messages KN R merges at distance i from the leaf be denoted by µ. If the packets that form the µ messages KN R merges arrive before the ν messages sent to the root separately the claim follows directly from Lemmas 4.6 and 4.7. Otherwise we have to take the delay cost the ν messages can save since the to be merged messages can arrive closer to each other into account. Applying Lemmas 4.6 and 4.7 leads to a total cost for KN R of less than 3(νhc + hc + µic) and the total cost for OPT amounts to at least Ω hc + min(ν 2 c, νhc) + µic . As in the proofs above we can assume without loss of generality that (ν + µ) ∈ ω( √ h). If νh < ν 2 the competitive ratio is O(1), otherwise the ratio is at most O( νh+µ h+ν 2 +µ ). Assume ν to be lager than µ. This implies that ν > √ h and hence the ratio is O(νh/ν 2 ) = O( √ h). If µ is larger than ν, we have a ratio of O(hnµ/(h + nµ 2 )), which is O(

√ h). 2
Hence, we have shown that the competitive ratio does not deteriorate for one occurrence of a merge operation. We can apply the above lemma and induction on the number of merge operations one message takes part in: Treat the node where a merge occurs as a new leaf node and consider the merge operations on the remaining chain until the root independently. For this network, the same arguments apply, and we can conclude that the cost the online and the offline algorithm save by merging does not inflict a change in the competitive ratio. Hence it follows that the competitive ratio is at most O(min( √ h, c)) on chain graphs.

Lower Bound

We now show that KN R is asymptotically optimal for all oblivious online algorithms, i.e., we derive a lower bound for chain networks of Ω(min( √ h, c)).

Theorem 4.9 The competitive ratio of any oblivious algorithm ALG is at least

ρ = cost ALG cost OPT ∈ Ω min( √ h, c) .
Proof: Let ALG denote any oblivious online algorithm, and assume that packets arrive one-by-one: At time 0, a packet p arrives at the leaf node l. The next packet arrives at the leaf exactly when ALG sends the packet at l. Let w denote the time a packet waits at l, and observe that the same waiting time holds for all nodes on the way from the leaf to the root due to the oblivious nature of ALG. Thus, the total waiting time per packet is hw, and the communication cost is hc: cost ALG = hw + hc. We now derive an upper bound on the optimal algorithm's cost for this sequence. We partition the packets into blocks of size √ h, i.e., one message contains √ h packets. Thus, the communication cost per packet of this algorithm is hc/

√ h = √ hc.
The delay cost per message at the leaf is

√ h-1 i=1
iw ∈ Θ(hw). In addition, each packet experiences one unit of delay per hop on the way up to the root. Thus, the optimal cost per packet is cost OPT ≤ Θ(

√ hc + w √ h + h).
Therefore, it asymptotically holds for this sequence that

ρ ≥ hc + hw √ hc + w √ h + h = h(c + w) √ h(c + w) + h .
The lower bound follows from distinguishing three cases. If h and c + w are asymptotically equivalent, this yields Ω( √ h). If h is asymptotically larger than c + w, the best oblivious algorithm choosing w as small as possible gives a lower bound of Ω (c). Finally, if h < c + w, we have Ω( √ h). 2

Discussion

Compared to the trees studied in the previous section, the analysis of chain networks is more involved. This can be explained with the fact that the tree bound is in the order of the tree height and hence merely investigating the cost occurring at any given depth rather than on the whole path is sufficient to prove the claim; there is no need to perform a detailed comparison of merge sequences of the online algorithm and the offline algorithm.

Our findings can be compared to the analysis presented in [START_REF] Khanna | Control Message Aggregation in Group Communication Protocols[END_REF]. Their Ω( √ h) lower bound holds for arbitrary oblivious algorithms on trees. We have shown that this upper bound is too pessimistic, as general trees are inherently more difficult than chain topologies, and that the lower bound can be increased to Ω(min(h, c)). For chain networks, we have generalized their result to arbitrary edge cost, yielding a lower bound of Ω(min( √ h, c)), which is proved tight by KN R.

Value-Sensitive Aggregation

There are many scenarios where, in contrast to the aggregation model considered above, the information to be delivered is not binary (e.g., event messages) but where arbitrary value aggregations need to be performed at the root. E.g., consider a set of sensor nodes measuring the temperature or oxygen levels at certain outdoor locations, and the root is interested to have up-to-date information on these measurements. In this case, larger value changes are more important and should be propagated faster to the root, e.g., such that an alarm can be raised soon in case of drastic environmental changes.

In the following, we consider a most simple topology: A network consisting of a leaf and a sink. Let the value measured by the leaf l at time t be l t . We assume that the leaf node can only send the value it currently measures. The root node's latest value of node l at time t is denoted by r t . We seek to minimize the following optimization function: cost = M • c + t |l t -r t | where M is the total number of message transmissions and c the cost per transmission, i.e., M • c is the total communication cost. We refer to the sum t |l t -r t | as the error cost.

Typically, the values measured by a sensor node do not change arbitrarily, but there is a bound on the maximal change per time unit. In the following, we assume that the value measured by a node changes by at most ∆ per time slot. Moreover, we assume that the sensor nodes can only measure discrete quantities, and that the difference between two measured values is at least .

Optimal Offline Algorithm for Link

There exists a simple optimal (offline) algorithm OPT which applies dynamic programming. OPT exploits the following optimal substructure: If we know the best sending times for all slots t < t given that a message is sent at time t , we can compute the optimal sending times assuming that OPT sends at time t. Let the number of time slots under scrutiny be T . Note that, we only have to consider the time slots with value changes, because an optimal algorithm either sends a value immediately after it has changed or not until the value has changed again. Let time slot t i denote the time slot when the i th value change occurred and we set t 0 = 0. Determining all time slots with value changes requires iterating over all T time slots. To compute the minimum cost accumulated until time slot t i , we consider each possible last transmission j < i and add the inaccuracy cost which accrued at the root node between the two transmissions j and i. Hence we can construct an array OP T [•] of size λ + 1, where λ is the total number of value changes at the leaf node. We set OP T [0] = 0, as we assume that initially, the root stores the correct value. The remaining matrix entries are then computed as follows:

OP T [i] = min j<i   OP T [j] + c + |l ti -l tj | + i-1 k=j+1 |l t k -l tj |(t k+1 -t k )   . In time O(λ 2 ) we construct a matrix A[•][•] of size (λ + 1) × (λ + 1)
, where for all 1 ≤ j, i ≤ λ the entry A i,j = |l ti -l tj |(t i+1 -t i ). This allows us to compute any sum

i-1 k=j+1 |l t k -l tj |(t k+1 -t k ) for 1 ≤ i ≤ j ≤ λ in constant time. For a given i, 1 ≤ i ≤ λ, computing OP T [i]
takes time O(λ) using these pre-computed values. Thus, we have the following theorem.

Theorem 5.1 In a link network, the optimal aggregation strategy for T time slots can be computed in time O(T + λ 2 ), where λ is the number of value changes at the leaf.

If the input for the offline algorithm consists of a sequence of value changes and the time slots when they happened, the time complexity is O(λ 2 ).

Theorem 5.3 The competitive ratio of AGG is

ρ = cost AGG cost OPT ∈ Θ(c/ ),
where c is the link cost and is the minimum difference between two values.

Proof: Upper bound. First, the ratio is computed under the assumption that the error cost of AGG is exactly c; we then apply Lemma 5.2. We classify the possible types of periods I between two sending events of the online algorithm and consider them separately. Observe that for any period where the optimal algorithm OPT transmits, the competitive ratio is at most 2, as OPT has cost at least c and the online algorithm AGG has communication cost c and error cost c. It remains to examine the situations where OPT does not send. Assume that at the beginning of this period, AGG sends the value A 0 , and at the end, it sends the value A 1 . Furthermore we denote the optimal algorithm's value at the root at the beginning and at the end of this period by O 0 and O 1 , respectively. We define δ 0 := |A 0 -O 0 | and δ 1 := |A 1 -O 1 | and examine all possible cases under the assumption that the error cost of AGG is c for every period.

Case δ 0 = δ 1 = 0: If OPT has no transmission, it must have the same error cost in this period as AGG, because the initial and final values are the same, and hence ρ I ≤ 2.

Case δ 0 = 0, δ 1 = 0: If OPT has no transmission, it must have at least the same error cost as AGG in I , thus ρ I ≤ 2.

Case δ 0 = 0, δ 1 = 0: If OPT has no transmission, it incurs at least error cost δ 0 in the first time slot, as AGG sends the correct value at the beginning of the period. Hence, ρ I ≤ 2c/δ 0 .

Case δ 0 = 0, δ 1 = 0: In this case, OPT has error cost δ 0 as well yielding ρ I ≤ 2c/δ 0 . Thus, for each of these periods, ρ I ≤ 2c/δ 0 . It must hold that δ 0 > , and the claim follows by applying Lemma 5.2.

Lower bound. Consider the following sequence of values at the leaf node: 0, c/ , 0 c/ -1 , -, 0 c/ -1 , , 0 c/ -1 , -, . . .

where α β denotes that the value α remains for β time slots. Observe that for each subsequence (0 c/ -1 , -, 0 c/ -1 , ),

2 is an upper bound on OPT 's delay cost: It is the total delay cost if there are no transmissions at all in the entire sequence. In contrast, AGG has 2c delay cost plus two transmissions. Thus, neglecting the cost of the first time slot, we have ρ ≥ 4c/2 = 2c/ . 2

Please note that the lower bound in Theorem 5.3 only holds for our algorithm AGG. The analysis of the claim for arbitrary algorithms is left for future research.

Conclusion

This article attended to the subject of online information aggregation, which can be regarded as a generalization of the classic ski-rental problem to trees. The studied optimization problem captures the trade-off between speed and energy prevalent in many wireless networks. We were able to show that a most simple algorithm achieves a best possible asymptotic competitive ratio in the class of oblivious, deterministic and fully distributed algorithms. In particular, the algorithm we consider fulfills its task without knowledge of the presence and the state of devices in its vicinity, and it does not base its decisions on previous events. Thus, apart from the efficiency criterion, the new analysis we have presented in this work suggests that the algorithm introduced in [KNR02] is attractive for practical applications as it poses minimal hardware requirements on sensor nodes in terms of computational requirements. Observe however that we assume that bursty arrivals of events and packets can be handled by the nodes. An interesting future research direction would be to allow nodes to inform their children that a certain packet could not be accepted due to memory constraints, and should be re-sent later. This makes the protocol more complex and requires nodes to know more about each other's state. Moreover, while such a solution can mitigate a problem in the short run, there is a natural bound on what can be stored in the total network with backlogging, namely the overall storage capacity of the nodes.

Acknowledgments

We would like to thank Thibaut Britz and Marcin Bienkowski for interesting discussions on this work.

Online Algorithm for Link

We propose the following online algorithm AGG, which can be seen as a generalization of the algorithm KN R discussed in the previous sections: The leaf l sends the value it currently measures if and only if T t=τ |l t -l τ | ≥ c, where τ is the last time l has transmitted its value and T is the current time. For the analysis of AGG, we consider the time periods between two transmissions of AGG. For each such period, we can bound the competitive ratio yielding an overall competitive ratio. We first need the following helper lemma.

Lemma 5.2 Let ρ be the competitive ratio of AGG when AGG's error cost is c in each time period I, then 3ρ/2 is an upper bound on the total competitive ratio.

Proof: First observe that AGG can have a larger error cost than c in a period, e.g., if in a time slot where the accumulated error cost is c -ε for an arbitrarily small ε > 0 there is a large value change of size ∆ at the leaf. Hence, the online algorithm's error in any period is at most 2(c -) + ∆. Consider a period I where the online algorithm's error cost is 2(c -) + k for some k ≤ ∆. Compared to the case studied so far, AGG's error cost will increase by at most k + c -2 . However, due to the large value change, we know that the optimal algorithm's error cost must increase by at least k as well. The new competitive ratio ρ is hence