Prosenjit Nicolas Bonichon

Prosenjit Bose

Jean-Lou De Carufel

Vincent Despré

Darryl Hill

Michiel Smid

Jean-Lou Bose

Vincent De Carufel

Darryl Despré

Hill

Improved Routing on the Delaunay Triangulation

Keywords: 2012 ACM Subject Classification Mathematics of computing → Paths and connectivity problems, Mathematics of computing → Graph algorithms Delaunay, local routing, geometric, graph Digital Object Identifier 10.4230/LIPIcs.ESA.2018.22

A geometric graph G = (P, E) is a set of points in the plane and edges between pairs of points, where the weight of an edge is equal to the Euclidean distance between its two endpoints. In local routing we find a path through G from a source vertex s to a destination vertex t, using only knowledge of the current vertex, its incident edges, and the locations of s and t. We present an algorithm for local routing on the Delaunay triangulation, and show that it finds a path between a source vertex s and a target vertex t that is not longer than 3.56|st|, improving the previous bound of 5.9|st|.

Introduction

A Euclidean geometric graph G = (P, E) is a set P of points embedded in the plane, and a set E of edges, where each e ∈ E is a pair of points (u, v) in P , and the weight of e is the Euclidean distance |uv|.

A local routing algorithm A is an algorithm that routes a packet through the geometric graph G from a source vertex s to a target vertex t using only knowledge of the locations of s and t, as well as the location of the current vertex and its adjacent vertices. Let P s, t be the path found in G from s to t using A. The routing ratio of A for any two points s and t in the geometric graph G is the ratio of the length of P s, t to the Euclidean distance from s to t. An algorithm A has a routing ratio c for a class of geometric graphs G, if, for any two vertices s and t in G ∈ G, |P s, t | ≤ c • |st|.

A graph G = (P, E) is a c-spanner if for any pair of points u and v in P the shortest path in G is not longer than c|uv|. The value c is referred to as the stretch factor or spanning ratio of G. The stretch factor of G is thus a lower bound on the routing ratio of G for any routing algorithm A, and the routing ratio is an upper bound on the spanning ratio of G. Geometric spanners are described in detail in the book by Narasimhan and Smid [START_REF] Narasimhan | Geometric Spanner Networks[END_REF].

A notable geometric graph is the Delaunay triangulation. Given a set P of points in the plane, we construct the Delaunay triangulation of P as follows. For each triple (p, q, r) of points in P , let C be the circle through p, q, and r. If there are no points of P in the interior of C, then we connect p, q, and r by edges to form a triangle. In this paper we assume that P is in general position: no 3 points are colinar and no 4 points are cocircular.

The Delaunay triangulation was first proven to be a spanner by Dobkin et al. [START_REF] Dobkin | Delaunay graphs are almost as good as complete graphs[END_REF], who showed an upper bound of 5.08 on the spanning ratio. This was subsequently improved to 2.42 by Keil and Gutwin [START_REF] Keil | Classes of graphs which approximate the complete euclidean graph[END_REF], and then to 1.998 by Xia [START_REF] Xia | Improved upper bound on the stretch factor of Delaunay triangulations[END_REF]. Xia and Zhang proved later that there exist Delaunay triangulations with spanning ratio greater than 1.59 [START_REF] Xia | Toward the tight bound of the stretch factor of Delaunay triangulations[END_REF].

Bose and Morin [START_REF] Bose | Online routing in triangulations[END_REF] explored some of the theoretical limitations of routing, and provided some of the first deterministic routing algorithms with constant routing ratio on the Delaunay triangulation. They denoted the spanning ratio found by Dobkin et al. [START_REF] Dobkin | Delaunay graphs are almost as good as complete graphs[END_REF] as c df s ≈ 5.08. They showed that it is possible to locally route on the Delaunay triangulation with a routing ratio of 9 • c df s ≈ 45.749. Bose et al. [START_REF] Bose | Competitive online routing on Delaunay triangulations[END_REF] further improved this bound to ≈ 15.479. Then, Bonichon et al. [START_REF] Bonichon | Upper and lower bounds for online routing on Delaunay triangulations[END_REF] showed that we can locally route on the Delaunay triangulation with a routing ratio of at most 5.9. In the same paper it was shown that the routing ratio of any deterministic local algorithm is at least 1.70 for the Delaunay triangulation.

Efforts to evaluate the spanning ratio and routing ratio have been made for Delaunay triangulations defined on other metrics. We can define these metrics by taking a convex shape and translating and scaling it until it intersects three vertices but contains no points of P in its interior. When we use a circle we obtain the L 2 , or classical Delaunay triangulation. When the metric is not specified (as in the rest of this paper), then we are referring to the L 2 -Delaunay triangulation. The L 1 -Delaunay triangulation uses an axis aligned square, while the L ∞ -Delaunay triangulation uses a square tipped at 45 degrees. By rotating the point set 45 degrees, it is easy to show that the L 1 and L ∞ triangulations are equivalent. Bonichon et al. [START_REF] Bonichon | Tight stretch factors for L 1 and L ∞ Delaunay triangulations[END_REF] showed that the L 1 and L ∞ Delaunay triangulations are 4 + 2 √ 2 ≈ 2.61-spanners, and they showed that this bound is tight. On this triangulation, Chew [START_REF] Chew | There is a planar graph almost as good as the complete graph[END_REF] proposed a routing algorithm with routing ratio √ 10. Moreover, the routing ratio of any deterministic local algorithm is at least 2.70 for this class of graph [START_REF] Bonichon | Upper and lower bounds for online routing on Delaunay triangulations[END_REF]. The TD-Delaunay triangulation is constructed using an equilateral triangle. Chew [START_REF] Chew | There are planar graphs almost as good as the complete graph[END_REF] showed that they are 2-spanners. Bose et al. [START_REF] Bose | Competitive routing in the half-theta-6-graph[END_REF] proposed a routing algorithm of routing ratio 5/3 ≈ 2.89 and they show that this ratio is the best possible. Recently Dennis, Perkovic and Duru [START_REF] Dennis | The stretch factor of hexagon-Delaunay triangulations[END_REF] showed that the stretch factor of Hexagon-Delaunay triangulation is 2 and this is tight. In this paper we present a local routing algorithm, called MixedChordArc, for the L 2 -Delaunay triangulation, with a routing ratio of 3.56. This improves the current best routing ratio of 5.9 [START_REF] Bonichon | Upper and lower bounds for online routing on Delaunay triangulations[END_REF]. Table 1 shows our result in the context of spanning and routing ratios of other Delaunay triangulations.

In Section 2 we define a local algorithm that achieves this routing ratio. In Section 3 we prove the result for a special case, called balanced configurations. In Section 4 we extend the technique presented in Section 3 to prove the main result in the general case. In Section 5 we present our conclusions and our ideas for future directions for this line of research.

2

The MixedChordArc Algorithm

Let P be a finite set of points in the plane, and let DT (P ) be the Delaunay triangulation of P . We want to route a packet between two vertices of P along edges of DT (P ) using only local knowledge and knowledge of our start and destination vertices.

Let s and t be the start and terminal vertices respectively, and assume, without loss of generality, that s and t are on the x-axis with s to the left of t. Our general position assumption ensures that no other vertex lies on st. Consider two triangles T and T whose interior is cut by st. We say that T is to the left of T , and T is to the right of T , if, by following st starting at s we intersect T before T . If uv is the edge shared by T and T , then our general position assumption ensures that u and v are on opposite sides of st.

Let C be a circle that intersects st. We denote by t C the rightmost point of C on st. Let u and v be two points on C. We denote by A C (u, v) the clockwise arc of C from u to v, and by B C (u, v) the counter-clockwise arc of C from u to v. We denote the length of a continuous curve S by |S|.

Let p = t be the vertex representing the current location of the packet. We assume s to be above st, and we assume t to be on the opposite side of st from the current vertex. Let T be the rightmost triangle with p as a vertex whose interior is cut by st. Let a = p be the vertex of T that is above st, and let b = p be the vertex of T that is below st. Let C be the circumcircle of T .

Here is the algorithm MixedChordArc. First assume that p = s.

If |A C (s, t C )| ≤ |B C (s, t C )|,
a. If |A C (p, t C )| ≤ |pb| + |B C (b, t C )|, set p = a b. Else set p = b. 2. If p is below st: a. If |B C (p, t C )| ≤ |pa| + |A C (a, t C )|, set p = b b. Else set p = a.
Note that assuming that t is on the opposite side of st from p ensures that when t is a neighbour of the current vertex, the algorithm will forward the packet directly to t.

The possible choices are illustrated in Fig. 1. Let P s, t = (s = p 0 , p 1 , ..., p n = t) be the sequence of vertices produced by the algorithm. In this paper we prove the following theorem.

Theorem 1. The MixedChordArc Algorithm finds a path P s, t from s to t whose length |P s, t | is not more than µ|st|, where µ = In some cases, the path produced by our algorithm is a balanced configuration. In such cases, the analysis of the length of P s, t is much easier. In Section 3 we define what a balanced configuration is, and analyze the length of P s, t for this specific case. Then, in Section 4, we analyze the length of P s, t for the general case.

Bounding |P s, t | in a Balanced Configuration

Let us consider a path P s, t of vertices such that p 0 = s, p n = t and p i-1 p i is an edge of the rightmost triangle T i of p i-1 that has a non-empty intersection with st. Let a i and b i be the other two vertices of T i , where a i is above st, and b i is below st.

Thus p i = a i or p i = b i . Let s = p 0 = a 0 = b 0 and let t = p n = a n = b n . Let C i be the circumcircle of T i , let
r i be its radius and let c i be its center. Let C 0 be the circle centered at s with radius r 0 = 0. Let T = (T 1 , T 2 , ..., T n ), and let C = (C 0 , C 1 , ..., C n ) be the sequence of circles starting at C 0 , followed by the circumcircles of T . Note that the vertex of T i that is on the opposite side of st to p i-1 may not be at the intersection of C i-1 and C i . Thus we define a second intersection point of C i-1 and C i as follows (p i-1 being one intersection point). If p i-1 is above st, then q i is the lowest intersection of C i and C i-1 (where "lowest" is defined by the point having the least y-coordinate). If p i-1 is below st, let q i be the highest intersection of C i-1 and C i (where "highest" is defined by the point having the greatest y-coordinate).

Note that it is possible to have C i-1 and C i intersect in two points, and still have

q i = p i-1 . See circle C 4 in Fig. 2.
Observe that if T i and T i-1 share an edge, then q i is the vertex of T i on the opposite side of st from p i-1 . See circles C 1 , C 2 , C 3 , and C 5 in Fig. 2. To simplify the notation, we write t i instead of t Ci , and we write

A i (u, v) and B i (u, v) instead of A Ci (u, v) and B Ci (u, v), respectively.
We say that a pair of consecutive circles For the rest of this section, we assume that P s, t is a balanced configuration. Consider the case when p i-1 is above st (the case when

C i-1 and C i is balanced if |A i (p i-1 , t i )| = |p i-1 q i | + |B i (q i , t i )| when p i-1 is above st, and if |B i (p i-1 , t i )| = |p i-1 q i | + |A i (q i , t i )| when p i-1 is below st. A path P s, t on a point set P is a balanced configuration when C i-1 and C i are balanced for all 1 ≤ i ≤ n.

Analysis Technique

Lemma 2. Let C i-1 and C i be arbitrary circles of C, where 1 ≤ i ≤ n. Then 1. |p i-1 b i | + |B i (b i , t i )| ≤ |p i-1 q i | + |B i (q i , t i )| when p i-1 is above st, and 2. |p i-1 a i | + |A i (a i , t i )| ≤ |p i-1 q i | + |A i (q i , t i )| when p i-1 is below st.

Proof. By the triangle inequality we have |p

i-1 b i | ≤ |p i-1 q i | + |B i (q i , b i )|, from which 1 follows. Case 2 is symmetric. q 0 , p 0 , t 0 , s p 1 , a 1 C 1 C 2 C 3 C 4 p 2 , a 2 p 3 , a 3 , q 4 b 1 , b 2 , b 3 , q 1 , q 2 , q 3 b 4 , p 4 a 4 q 5 b 5 , p 5 , t 5 , t
p i-1 is below st is symmetric). If q i = b i then |A i (p i-1 , t i )| = |p i-1 b i | + |B i (b i , t i )|,

and the algorithm proceeds to a

i . If q i = b i , observe that |p i-1 b i | ≤ |p i-1 q i | + |B i (q i , b i )|
by the triangle inequality (see circles C 4 and C 5 in Fig. 2). Let x(v) and y(v) be the x and y-coordinates of a point v, respectively. Let s i be a point on st such that x(s i ) = x(t i ) -2r i . We define the following potential function that we use to bound the length of P s, t .

Thus we have |p

i-1 b i | + |B i (b i , t i )| < |p i-1 q i | + |B i (q i , t i )| = |A i (p i-1 , t i )|,
Definition 3. If p i-1 is above st, then Φ(C i-1 , C i ) = |A i (p i-1 , t i )| -|A i-1 (p i-1 t i-1 )| -λ|s i-1 s i | -(µ -λ)|t i-1 t i |. Otherwise, if p i-1 is below st, then Φ(C i-1 , C i ) = |B i (p i-1 , t i )| -|B i-1 (p i-1 t i-1 )| -λ|s i-1 s i | -(µ -λ)|t i-1 t i |,
where λ = 1+sin (1) cos(1) -π/2 -1 /2 ≈ 0.42 and µ = Lemma 6. For any C, x(t i-1 ) < x(t i ) for all 1 ≤ i ≤ n, and

n i=1 |t i-1 t i | ≤ |st|.
Proof. We prove that x(t i-1 ) < x(t i ), that is, t i is right of t i-1 for all 1 ≤ i ≤ n, by contradiction. Assume that x(t i-1 ) ≥ x(t i ). If q i is to the same side of st as p i-1 , then C i-1 must contain the vertex of T i on the opposite side of st. If q i is on the opposite side of st as p i-1 , then C i-1 contains the vertex of T i on the same side of st as p i-1 . Both cases contradict the construction of a Delaunay triangulation. This, together with the fact that t 0 = s and t n = t implies the second part of the lemma. Proof. We first analyze the case when p i-1 is above st. Recall that in this case, Φ(

Lemma 7. For 1 ≤ i ≤ n, if p i-1 is above st, then 1. a. |A i (p i-1 , t i )| > |p i-1 p i | + |A i (p i , t i )| if p i is above st, and b. |A i (p i-1 , t i )| > |p i-1 p i | + |B i (p i , t i )| if p i is below st otherwise p i-1 is below st and 2. a. |B i (p i-1 , t i )| > |p i-1 p i | + |B i (p i , t i )| if p i is below st, and b. |B i (p i-1 , t i )| > |p i-1 p i | + |A i (p i , t i )| if p i is above st. Proof. Case 1a is because |A i (p i-1 , p i )| > |p i-1 p i |,
C i-1 , C i ) is defined as Φ(C i-1 , C i ) = |A i (p i-1 , t i )| -|A i-1 (p i-1 t i-1 )| -λ|s i-1 s i | -(µ -λ)|t i-1 t i |.
If p i is above st (same side of st as p i-1 ), then

|A i (p i-1 , t i )| > |p i-1 p i | + |A i (p i , t i )| by Lemma 7. In this case, let D i = A i (p i , t i ). If p i is below st, then |A i (p i-1 , t i )| > |p i-1 p i | + |B i (p i , t i )| by Lemma 7. In this case, let D i = B i (p i , t i ). In both cases we have |A i (p i-1 , t i )| > |p i-1 p i | + |D i |. Let Φ (C i-1 , C i ) be the function defined by Φ (C i-1 , C i ) = |p i-1 p i | + |D i | -|D i-1 | -λ|s i-1 s i | -(µ -λ)|t i-1 t i |. p i-1 C i-1 C i Di-1
Ai(pi-1, ti)

q i t i-1 t i s i s i-1
Figure 4 Illustrating the function Φ(Ci-1, Ci): blue minus green is charged to red to obtain an upper bound on the routing ratio.

Observe that Φ (C

i-1 , C i ) ≤ Φ(C i-1 , C i ). By Lemma 4, Φ(C i-1 , C i ) ≤ 0, thus Φ (C i-1 , C i ) ≤ 0. When p i-1 is below st, a symmetric proof again shows us that Φ (C i-1 , C i ) ≤ 0. Recall that p 0 = t 0 = s, and p n = t n = t, which means |D 0 | = |D n | = 0. Therefore we have n i=1 Φ (C i-1 , C i ) ≤ 0 from which we get: n i=1 (|p i-1 p i | + |D i | -|D i-1 |) ≤ n i=1 (λ|s i-1 s i | + (µ -λ)|t i-1 t i |) |P s, t | -|D 0 | + |D n | ≤ (λ + µ -λ)|st| (1)
|P s, t | ≤ µ|st|.

The right hand side of ( 1) is due to Lemmas 5 and 6.

Lemma 5 is discussed in the next section. Lemma 4 is discussed in Section 3.3.

Proof of Lemma 5

Lemma 5 uses the following supporting result: Lemma 8. Let C i-1 and C i be balanced. Let s i-1 be the point on st where x(s i-1 ) = x(t i-1 ) -2r i-1 and let s i be the point on st where x(s i ) = x(t i ) -2r i . Then x(s i-1 ) ≤ x(s i ).

Proof. See Fig. 5. Let u i-1 be the point on C i-1 that is diametrically opposed to t i-1 and let u i be the point on C i that is diametrically opposed to t i . We will show the case when p i-1 is above st; the case when it is below st is symmetric. Since C i-1 and C i are balanced, we have that

|A i (p i-1 , t i )| = |p i-1 q i | + |B i (q i , t i )| which implies that |A i (p i-1 , t i )| ≤ πr i and |B i (q i , t i )| ≤ πr i . Since |A i (u i , t i )| = |B i (u i , t i )| = πr i , u i is not on the open interval A i (p i-1 , t i ) or B i (q i , t i ),
which implies that either u i is on the arc of C i between p i-1 and q i that does not contain t i , or u i = p i-1 = q i . Lemma 6 implies that t i is not inside C i-1 , which implies that u i must be on or inside C i-1 . Let O i be the circle centered at t i with radius |t i u i | = 2r i . Thus O i and C i are tangent at u i , and O i intersects st at s i . Let O i-1 be the circle centered at t i-1 with radius 2r i-1 . Thus O i-1 and C i-1 are tangent at u i-1 , and O i-1 intersects st at s i-1 . We prove the lemma by contradiction, thus assume that E S A 2 0 1 8

22:8

Improved Delaunay Routing

s t C i t i u i p i-1 q i C i-1 s i s i-1 t i-1 O i O i-1 u i-1
Figure 5 Oi must intersect Oi-1 if Ci-1 and Ci are path balanced, which implies that x(si-1) ≤ x(si).

x(s i ) < x(s i-1 ). In the proof of Lemma 6, we showed that x(t i ) > x(t i-1 ). Therefore, it must be that O i-1 is in the interior of O i , and thus they do not intersect. Since u i is on or inside C i-1 , and

O i intersects u i , O i must intersect C i-1 . But C i-1 is contained in O i-1
except for the point u i-1 , and O i-1 is contained in O i , and thus O i cannot intersect C i-1 , which is a contradiction. See Fig. 5.

We can now prove Lemma 5:

Proof of Lemma 5. Follows from Lemma 8 and the fact that x(s 0 ) = x(s) and x(s n ) < x(t).

C i-1 C i st D i-1 p i-1 q i s i s i-1 c i-1 c i t i-1 t i A i (p i-1 , t i )
Figure 6 Coordinate system for analyzing Φ(Ci-1, Ci).

Proof of Lemma 4

To show that Φ(C i-1 , C i ) ≤ 0 when C i-1 and C i are balanced, we set up the following coordinate system. We show the proof for the case when p i-1 is above st; the case when p i-1 is below st is symmetric. Let c i-1 and c i lie along the x-axis, and let p i-1 and q i lie along the y-axis. See Fig. 6. Lemma 4 follows from the following two lemmas:

Lemma 9. When C i-1 and C i are balanced, if y(t i-1 ) ≤ 0, then Φ(C i-1 , C i ) ≤ 0. Lemma 10. When C i-1 and C i are balanced, if y(t i-1 ) > 0, then Φ(C i-1 , C i ) ≤ 0.
The main tool to prove these two lemmas is the following transformation, which is similar to a transformation used by Xia [START_REF] Xia | Improved upper bound on the stretch factor of Delaunay triangulations[END_REF].

Transformation 11. Fix p i-1 and q i , and translate c i to the left along the x-axis until c i = c i-1 . Moreover keep C i-1 unchanged and maintain C i as the circle with center c i with p i-1 on its boundary.

Observe that, after we have completed Transformation 11, we have Transformation 11. Thus we wish to find the change in Φ(C i-1 , C i ) with respect to the change in x(c i ) during Transformation 11. Formally:

C i = C i-1 and thus Φ(C i-1 , C i ) = 0. If we can show that Φ(C i-1 , C i ) is increasing while x(c i ) decreases, then it must be that Φ(C i-1 , C i ) ≤ 0 before
Lemma 12. If dΦ(Ci-1,Ci) dx(ci) ≤ 0 during Transformation 11, then Φ(C i-1 , C i ) ≤ 0.

Proof. At the end of Transformation 11 we have that Φ(C

i-1 , C i ) = 0. If dΦ(Ci-1,Ci) dx(ci) ≤ 0 then Φ(C i-1 , C i ) is not decreasing during Transformation 11, and thus Φ(C i-1 , C i ) ≤ 0 before Transformation 11.
The analysis of this function is similar to Xia's approach [START_REF] Xia | Improved upper bound on the stretch factor of Delaunay triangulations[END_REF]. To ensure that this transformation is well-defined, we require q i to be below st. We observe that Φ(C i-1 , C i ) is maximized when st is on or above c i-1 , and this assumption implies q i is below st (or on st, in the case where p i-1 = q i ). Full details of this analysis, the transformation analysis, and the proofs for Lemmas 9 and 10 have been left out due to space constraints.

4

Bounding P s, t in the General Case

In Section 3, we proved Theorem 1 for the case when the path produced by our algorithm results in a balanced configuration. In this section, we prove Theorem 1 for the general case. Given a sequence C of circles that intersect st, no series of transformations were found that could achieve a balanced configuration, while simultaneously providing a provable upper bound on the length of |p i-1 , p i |. However, we were able to find two sequences of circles to substitute for C. To represent each C i in C, we have a potential circle C P i and a bounding circle C B i . Like C i , both C P i and C B i have t i as their rightmost intersection with st. However, C i intersects both p i and p i-1 , while C B i is only required to intersect p i-1 , and C P i is only required to intersect p i . If we look at a bounding circle C B i and the previous potential circle C P i-1 , which intersect at p i-1 , they are balanced, and we can thus apply the function Φ(C P i-1 , C B i ) to relate the lengths of the arcs of these circles to |st|. Finally, when analyzed properly, they provide an upper bound on the length |p i p i-1 |.

Formally, let C P 0 be the circle centered at s = p 0 with radius r P 0 = 0, and let C P n be the circle centered at t with radius r P n = 0. Assuming we have defined C P i-1 , we will define C B i and

C P i . If p i-1 is above st, let C B i be the circle through p i-1 and t i for which |A C B i (p i-1 , t i )| = |p i-1 q i | + |B C B i (q i , t i )|
, where q i is the bottommost intersection t, p 6 , t 6 of Due to space constraints, we omit the proof of the following lemma.

p 1 p 2 p 3 p 4 p 5 s, p 0 A B 1 (p 0 , t 1 ) A B 2 (p 1 , t 2 ) A B 3 (p 2 , t 3 ) B B 4 (p 3 , t 4 ) A B 5 (p 4 , t 5 ) B B 6 (p 5 , t 6 ) D P 1 D P 2 D
C P i-1 and C B i . If p i-1 is below st, let C B i be the circle through p i-1 and t i for which |B C B i (p i-1 , t i )| = |p i-1 q i | + |A C B i (q i , t i )|,
P i-1 , C B i ) = |A B i (p i-1 , t i )| -|A P i-1 (p i-1 , t i-1 )| -λ|s P i-1 s B i | -µ|t i-1 t i | when p i-1 is above st and Φ(C P i-1 , C B i ) = |B B i (p i-1 , t i )| -|B P i-1 (p i-1 , t i-1 )| -λ|s P i-1 s B i | -µ|t i-1 t i | when p i-
Lemma 14. For 1 ≤ i ≤ n, if p i-1 is above st, then 1. a. |A B i (p i-1 , t i )| ≥ |p i-1 p i | + |A P i (p i , t i )| if p i is above st, and b. |A B i (p i-1 , t i )| ≥ |p i-1 p i | + |B P i (p i , t i )| if p i is below st otherwise p i-1 is below st and 2. a. |B B i (p i-1 , t i )| ≥ |p i-1 p i | + |B P i (p i , t i )| if p i is
P i-1 , C B i ) = |p i-1 p i | + |D P i | -|D P i-1 | -λ|s P i-1 s B i | -(µ -λ)|t i-1 t i |.
Lemmas 14 and 4 imply that Φ (C

P i-1 , C B i ) ≤ Φ(C P i-1 , C B i ) ≤ 0. Using Φ (C P i-1 , C B i ) we get: n i=1 Φ (C i-1 , C i ) ≤ 0 n i=1 |p i-1 p i | + |D P i | -|D P i-1 | ≤ n i=1 (λ|s P i-1 s B i | + (µ -λ)|t i-1 t i |) |P s, t | -|D P 0 | + |D P n | ≤ (λ + µ -λ)|st| (2) |P s, t | ≤ µ|st|.
Line (2) follows from Lemmas 6 and 13.

We give some insight into the selection of r P i . Assume that p i-1 is above st (when p i-1 is below st the explanation is symmetric). The purpose of

|A B i (p i-1 , t i )| is to bound |p i-1 p i | + |A P i (p i , t i )|,
P i-1 C i-1 C i p i-1 b i t i a i , p i t i-1
(a) Ci-1, Ci, and

C P i-1 . Notice that r P i-1 > ri-1. C P i-1 C i-1 C i C B i p i-1 b i q i t i a i , p i (b) C B i
and its intersection with

C P i-1 . C B i p i-1 q i t i A P i (p i , t i ) A B i (p i-

Conclusion and Future Work

Consider the algorithm presented in Section 2, along with two variations. To keep the algorithms simple, assume we are at a vertex p above st. Otherwise all assumptions are the same as in Section 2. The algorithm presented in this paper is M ixedChordArc. Following the techniques used in [START_REF] Bonichon | Upper and lower bounds for online routing on Delaunay triangulations[END_REF] we are able to show that the routing ratio of M inArc is between 3.20 and 3.96. Since the routing ratio of 3.56 of M ixedChordArc is better, we do not present the details of M inArc.

We suspect that BestChord is an improvement on M ixedChordArc. It seems plausible that we can modify the proofs presented in this paper to obtain the same upper bound for BestChord as for M ixedChordArc, but for now that remains unverified. Whether or not BestChord is asymptotically superior to M ixedChordArc, or whether they are asymptotically the same is still unknown.

Although we have improved the upper bound of the routing ratio on the L 2 -Delaunay triangulation, it is not clear how tight our analysis is. The upper bound on the analysis is where our potential function is the weakest. A more clever potential function could lower the routing ratio using a comparable analysis. Or perhaps one of the algorithms above would respond to a completely different style of analysis.

Furthermore, the lower bound on M ixedChordArc is still the same as the lower bound on routing on the L 2 -Delaunay triangulation in general, which is approximately 1.70 [START_REF] Bonichon | Upper and lower bounds for online routing on Delaunay triangulations[END_REF]. So it seems there is still much room for improvement. The question remains, what other algorithms or analysis can we use to improve the routing ratio of the Delaunay triangulation? And given that the upper and lower bounds on the spanning ratio of the L 2 -Delaunay triangulation are 1.998 [START_REF] Xia | Improved upper bound on the stretch factor of Delaunay triangulations[END_REF] and 1.5932 [START_REF] Xia | Toward the tight bound of the stretch factor of Delaunay triangulations[END_REF] respectively, is there a separation of the spanning and routing ratios of the Delaunay triangulation?

1 .

 1 set p = a, otherwise set p = b. See Fig.1a. If p = s, we repeat the following until p = t. If p is above st:

2 1 -

 1 sin(1) < 3.56. From p = s, the blue arc is shorter than the red arc, so we forward to a. From p, the blue path is shorter than the red path, so we forward to a. From p, the blue path is shorter than the red path, so we forward to a.

Figure 1

 1 Figure 1 Illustrating one step of the algorithm.

5 Figure 2

 52 Figure 2 Sequence of circles in a balanced configuration and the path in blue. The dotted circles are circumcircles of triangles intersected by st but not in T .

  and the algorithm proceeds to b i . Thus a balanced configuration allows for steps that cross st and steps that do not cross st. It also allows us to use |A i (p i-1 , t i )| as an upper bound on |p i-1 b i | + |B i (b i , t i )| in the case where p i-1 p i crosses st.

2 1 - 2 . 4 .Lemma 5 . 3 Figure 3

 124533 Figure3Illustrating the non-zero potential functions Di, 1 ≤ i ≤ 4 of a balanced configuration.

  The sequence of triangles T intersected by st, along with their circumcircles C, and the path P s, t found by the algorithm in bold.

5 ( b )

 5b The complete set of bounding arcs and potential arcs used in the function Φ(C P i-1 , C B i ), used to bound the routing ratio in the general case.

Figure 7

 7 Figure 7The initial circumcircles in 7a, and the construction of the potential circles and bounding circles in the general case in 7b.

A) BestChord:

  If |pa| + |AC (a, tC )| ≤ |pb| + |AC (b, tC )| then p = a else p = b. B) MixedChordArc: If |AC (p, tC )| ≤ |pb| + |AC (b, tC )| then p = a else p = b. C) MinArc: If |AC (p, tC )| ≤ πr then p = a else p = b.

Table 1

 1 Spanning and Routing Ratios of Delaunay Triangulations. Tight results are shown in bold.

	Graph T D-Delaunay L1 and L∞-Delaunay	Spanning Ratio 2 [8] 4 + 2 √ 2 ≈ 2.61 [3]	Routing Ratio 5/ √ 3 ≈ 2.89 [5] √ 10 ≈ 3.16 [7]
	Hexagon-Delaunay	2 [9]
	L2-Delaunay	1.998 [13]	3.56 (this paper)

  and Case 1b is because if p i is below st, then the algorithm chose to cross st, which implies 1b. Case 2 is symmetric.

	Theorem 1 follows from Lemmas 4, 5, 6, and 7:

  where q i is the topmost intersection of C See Figs. 7a and 7b for an example of the initial sequences T and C and the resulting bounding and potential arcs that we are interested in.

	Since C P i-1 and C B i are balanced, Φ can be extended to C P i-1 and C B i , and thus we have
	Φ(C
	P i-1 and
	C B i . That is, C P i-1 and C B i are balanced. Let r B i be the radius of C B i . The potential circle
	C P i is the circle through p i , whose rightmost intersection with st is t i , and whose radius is
	given by r P i = min{r i , r B i } (with the exception of r P n = 0). Let s P i be the point on st with
	x(s P i ) = x(t i ) -2r P i , and let s B i be the point on st with x(s B i ) = x(t i ) -2r B i .
	To simplify notation, for points u and v on C P i , instead of writing A C P i (u, v) and B C P i (u, v)
	to indicate clockwise and counter-clockwise arcs of C P i from u to v, respectively, we write
	A P i (u, v) and B P i (u, v). Likewise, for points u and v on C B i , instead of writing A C B i (u, v)
	and B C B i (u, v), we write A B i (u, v) and B B i (u, v).

  1 is below st. Lemma 4 tells us that Φ(C P i-1 , C B i ) ≤ 0. To prove Theorem 1 in the general case, it is sufficient to prove the following two lemmas. Lemma 13 is a generalization of Lemma 5, whereas Lemma 14 is a generalization of Lemma 7.

	Lemma 13.	n i=1 |s P i-1 s B i | ≤ |st|.
	Proof. Since C P i-1 and C B i are balanced, Lemma 8 tells us that x(s P i-1 ) ≤ x(s B i ). We know
	that x(s P i ) = x(t i ) -2r P i and x(s B i ) = x(t i ) -2r B i , thus the fact that r P i = min{r i , r B i }
	implies that x(s B i ) ≤ x(s P i ). Thus |s P i-1 s B i | ≤ |s P i-1 s P i |, and it is sufficient to show that n i=1 |s P i-1 s P i | ≤ |st|. The fact that x(s P i-1 ) ≤ x(s B i ) implies that x(s P i-1 ) ≤ x(s P i ), and C P 0
	is the circle centered at s with radius 0, and thus s P 0 = s. Since x(s P n ) ≤ x(t), this completes
	the proof.

  Theorem 1 follows from Lemmas 4, 6, 13, and 14. If p i is above st, let D P

	Proof of Theorem 1.

below st, and b. |B B i (p i-1 , t i )| ≥ |p i-1 p i | + |A P i (p i , t i )| if p i is above st. i = A P i (p i , t i ). If p i is below st, let D P i = B P i (p i , t i ). Let Φ (C

2 0 1 8 22:12 Improved Delaunay Routing C

  , it can happen that the arc |A B i+1 (p i , t i+1 )| on the next bounding circle is not large enough to cover |p i p i+1 | + |A P i+1 (p i+1 , t i+1 )|. See Fig. 8. Thus Lemma 14 would not hold. To account for this, we ensure that C P i has radius at most r i .

	as expressed in Lemma 14. This lemma is also the reason for selecting
	the radius of C P i as r P i = min{r i , r B i }. It would be simpler to let r P i = r B i , since then we
	would have s P i = s B i . However, if we allow r P i > r i

E S A

  The reasoning behind r P i = min{ri, r B i }. In this diagram, r P i > ri, and we show why it is detrimental to our analysis. Notice that |A B i (pi-1, ti)| < |pi-1, pi| + |A P i (pi, ti)|. Thus the arc A B i (pi-1, ti) of the bounding circle is not long enough to pay for |pi-1, pi| + |A P i (pi, ti)| .

	a i , p i
	1 , t i )
	C P
	i-1
	C P
	i
	(c) |A B i (pi-1, ti)| < |pi-1, pi|+
	|A P i (pi, ti)|.
	Figure 8

Funding This work was supported by the National Sciences and Engineering Research Council of Canada (NSERC) and by the French ANR grant ASPAG (ANR-17-CE40-0017)


Sourya Joyee De

Daniel Le Métayer
email: daniel.le-metayer@inria.fr

Privacy Risk Analysis to Enable Informed Privacy Settings

Keywords: privacy risk analysis, harm trees, privacy settings, quantified self, fitness tracking device

The work described in this paper is a contribution to enhancing individual control over personal data which is promoted, inter alia, by the new EU General Data Protection Regulation. We propose a method to enable better informed choices of privacy settings. The method relies on a privacy risk analysis parameterized by privacy settings. The user can express his choices, visualize their impact on the privacy risks through a user-friendly interface and, if needed, decide to revise them to reduce risks to an acceptable level.

I. INTRODUCTION

Users reveal a lot of personal data to various websites and service providers. Even if data controllers must, in most cases, obtain their consent before collecting their data, this consent is more a formal right than a true protection. The main reason is that data subjects do not have the time and expertise to read and understand the general terms of use or privacy policies of the data controllers.

Ideally, users' choices should be based on a clear appraisal of the risks and benefits of the available options. On the legal side, this view is supported by the EU General Data Protection Regulation (GDPR) [START_REF]679 of the European Parliament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF], which emphasizes control over personal data1 and states that data subjects should be made aware of the risks related to personal data processing 2 . In this paper, we propose a method, based on privacy risk analysis, to help users understand the privacy risks that may result from their choices of privacy settings. Our work relies on a privacy risk analysis methodology proposed in [START_REF] De | PRIAM: A Privacy Risk Analysis Methodology[END_REF], [START_REF] De | Privacy Harm Analysis: A Case Study on Smart Grids[END_REF]. The core of the approach is the construction and analysis of harm trees derived from information about the system, the personal data involved, the relevant risk sources, the feared events and their impacts in terms of privacy. The methodology is extended to take into account the privacy settings of the users and analyze their impact on the likelihood of privacy harms.

To illustrate our approach, we use as a case study a quantified self application. Quantified self is chosen both because of its fast growth and for the various privacy risks that such systems may pose to their users [START_REF] Field | Biggest Privacy Problems in Fitness Trackers Still To Come[END_REF], [START_REF] Oskolkov | Your fitness is their business. Nothing personal[END_REF], [START_REF] Hill | Fitbit Moves Quickly After Users' Sex Stats Exposed[END_REF]. Fitness tracker devices (e.g., Fitbit) allow their users to track their number of steps, strenuous activities, heart beats and location. They also provide users different types of derived information such as sleep patterns, calories burnt or goals achieved through a comprehensive dashboard. For the rest of this work, we consider a high-level specification of a fitness tracking system inspired by existing products, but we focus on a limited subset of functionalities for the sake of conciseness.

One of the desirable features of transparency enhancing technologies (TETs) targeted at data subjects is that they should be very user-friendly, with an easy-to-understand presentation of information about the privacy implications of different actions and possible choices [START_REF] Hedbom | A Survey on Transparency Tools for Enhancing Privacy[END_REF]. To address these needs, we also propose a user interface through which users can easily communicate to the service provider their preferences and visualize their impact on the likelihood of privacy harms.

We describe the preliminaries on privacy risk analysis (illustrated with our case study) in Section II, and discuss user privacy preferences in Section III. In Section IV, we design a user-friendly, interactive interface that enables users to define their privacy settings and understand the resulting privacy risks. In Section V, we "lift the hood" and present the engine used to compute privacy risks. Finally, we discuss related works in Section VI and conclude with perspectives in Section VII.

II. PRELIMINARIES

In this section, we present the terminology used in the rest of the paper and illustrate it with our case study. We stress the fact that the technical terms and notions presented here (including harm trees) are useful to the reader but do not have to be known by the users. Users interact with the system only through the interface presented in Section IV, which hides all technicalities.

A. Definition of the System

A fitness tracking service consists of a fitness tracking device TD for each user i. This device collects fitness data f it i and location data loc i . This data is then forwarded to the service provider to be stored and processed. Apart from owning the device itself, the user generally needs to create a personal user account UA where he must provide identification ID i and other information. The user must authenticate himself using his identification (ID i ) and password (pwd i ) to access his account. The fitness device owned by the user is linked to UA. The system provides comprehensive information about the level of fitness of the user through a personalized dashboard accessible through the user account. The service provider uses f it i and loc i to derive this fitness related information df it i (e.g. calories burnt, sleep pattern, active minutes and distance covered). Users can also maintain a list of contacts, share his data (df it i and loc i ) with them and see the data shared by the contacts. For simplicity, we assume that the service provider manages the application server AS where all data processing takes place and the database server DS which stores all data.

B. Definition of data

We assume that some data such as f it i and df it i may or may not be associated with the identity ID i and we use the notation x i to denote the pair (x i , ID i ) for conciseness. For example, the service provider may always store and process f it i but give access to only f it i to a third party.

The database server DS, which is a persistant storage, stores most types of data for user i in an encrypted format (ef it i , edf it i , eloc i ). It also stores the cryptographic keys k, k and the passwords pwd i . Password-protected data (pdf it i and ploc i ) are accessible through UA. Since the user knows the password, he can access df it i and loc i through UA. He can access data that dates back to one year or one week (depending again on the retention time).

Data processing takes place in the application server AS. The tracking device TD usually stores data for a short period of time (for e.g., seven days). In the sequel, this type of storage is called transient. In both AS and TD, data is stored in encrypted format for a short duration.

The service provider ensures that all data are protected by encryption and access control mechanisms. He also ensures the protection of cryptographic keys and passwords.

C. Definition of the risk sources

Risk sources either intentionally or unintentionally, legally or illegally cause privacy breaches [START_REF] De | PRIAM: A Privacy Risk Analysis Methodology[END_REF]. We consider the following risk sources for our case study3 : the system owner or service provider (A.1), friends of the user (A.2), hackers (A.3), the general public (A.4) and business partners of the service provider (e.g., insurance providers) (A.5).

D. Definition of the privacy harms

Fitness service providers may sell identifiable data to third parties such as health insurance providers who may use the user's fitness data to increase health insurance premiums (H.1). User's personal habits or health conditions may also become accessible to the public (H.2) due to hackers or via other means. We refer to such negative impacts on the data subjects as privacy harms [START_REF] De | PRIAM: A Privacy Risk Analysis Methodology[END_REF]. Other harms are also possible, but we do not discuss them here because of space limitations.

E. Definition of the feared events

Harms result from the combination of one or more feared events [START_REF] De | PRIAM: A Privacy Risk Analysis Methodology[END_REF] which are technical events of the system made possible by access to personal data (which we call "exploitation of data" here by analogy with the exploitation of vulnerabilities in computer security). Generally speaking, we distinguish three types of feared events resulting from, respectively, the access to personal data (FE.3), the use of personal data (FE.1), and the disclosure of personal data (FE.2).

F. Construction of the harm trees

A harm tree represents the relationships among privacy harms, feared events and the exploitation of personal data. The root node of a harm tree denotes a privacy harm. Leaf nodes represent the exploitation of data by the most likely risk source (for the root harm). They are represented as triples (personal data, system component, risk source). Intermediate nodes are feared events caused by risk sources. They can be seen as intermediate steps of privacy attacks. Child nodes are connected by an AND node if all of them are necessary to give rise to the parent node and by an OR node if any one of them is sufficient.

As an illustration, the harm trees pictured in Figure 1 and Figure 2 are assumed to result from a risk analysis (see Section V) conducted for our case study (for example in the context of an enhanced Data Protection Impact Assessment). Figure 1 shows that the harm increased health insurance premium (H.1) can be caused by the service provider disclosing to health insurance providers (FE.2) fitness related data (which may be done by disclosing either fitness data f it i , or other data that can reveal fitness data such as df it i in identified or de-identified form). Health insurance providers may use this data to increase health insurance premium (FE.1) for users who they deem unfit. To exploit de-identified data, the health insurance provider (A.5) must have access to identification (ID i ) information of the users as background information. Similarly, Figure 2 pictures the harm tree for H.2. Some combinations of risk sources and exploitations are very unlikely in practice. For example, friends (A.2) of the user are very unlikely to attack servers to get access to the data. These combinations are thus left out of the harm trees.

ID i may be obtained by a risk source either from a system component or as background information ("Bck" in harm trees). We assume that all other data elements can be obtained only from a system component (they are unlikely to be known as a background information by a risk source).

III. USER PRIVACY PREFERENCES

In this work, we assume that data subjects can specify their privacy preferences or privacy settings through privacy parameters. For the sake of conciseness, we consider only four privacy parameters for our case study:

1) The retention duration (Ret) of fitness (df it i , f it i ) and location data (loc i ) at the service provider's database (DS) and in the user account (UA). It can have two values: one year (L) and one week (S). The default value is: one week (S). The value of Ret for the components TD and AS are always short.

2) The visibility (Vis) of derived fitness (df it i ) and location data (loc i ) from the user account (UA). These data can be made visible to the public (P u) or friends (F ) or kept private (P r). The default value is: private (P r).

3) The recipients (Rec) of fitness (df it i , f it i ) and location data (loc i ) from the service provider. The service provider may choose to disclose these data only to his sub-contractors (DA) essential to provide the service or to any third party (All) for different incentives. The default value is: sharing only with sub-contractors (DA).

4) The form (Form) in which the service provider discloses fitness (df it i , f it i ) and location data (loc i ) to their recipients. The service provider can disclose these data in an identified form (Id) or disclose only de-identified data (deId). The default value is: disclosure of de-identified data (deId).

A user privacy preference is a conjunction of the values assigned to the privacy parameters. For example, the conjunction (Ret = L) ∧ (Rec = DA) ∧ (Vis = F ) ∧ (Form = deId) is a user privacy preference. The likelihood of the privacy harms may be affected by these preferences. Here, for simplicity, we assume that the user sets the same value for each parameter for all data elements. The default values of the privacy parameters are chosen such that they constitute the most protective privacy preference which is given by

(Ret = L) ∧ (Rec = DA) ∧ (Vis = F ) ∧ (Form = deId).

IV. USER INTERFACE DESIGN

The objective of this section is to show how users can be informed about the consequences of their privacy settings in a simple and intelligible way. Therefore, we focus on the user interface here and leave the presentation of the actual computation of the risks to the next section.

Users can express their privacy preferences through their account UA. The choices can be made when they initially open their account and set up their fitness tracking device.

Figure 3 shows the interactive screen using which users set their privacy preferences. Privacy preferences are displayed on the left pane, referred to as the privacy preference pane. For different privacy preferences selected by the user, the screen displays (prominently, on its right hand side) the risks that they may face. We refer to this pane as the privacy risk pane.

A. The Privacy Risk Pane

The right pane (see Figure 3) shows the users the risk levels corresponding to each harm. Each harm is presented using a short phrase that can be easily understood by the user. For example, the harm H.1 is presented as "Pay more health insurance premium". Below each harm, the risk level is presented as the likelihood and the severity of the harm, using coloured buttons. The likelihood of the harm is dependent on the user privacy preferences. In contrast, the severity results only from the nature of the harm. To explain to the user what these buttons mean, we colour and label them using very short text, both indicative of their meaning and also caption them with phrases like "How likely?" (referring to the likelihood) and "How severe?" (referring to the severity).

When a user changes his privacy setting, the colours and texts inside the button representing likelihood also change (see Section IV-C).

B. The Privacy Preference Pane

On the left pane of the screen, users are asked a series of questions to determine their privacy preferences. The questions are followed by alternatives which the users can select (by clicking on the corresponding radio buttons). The default selection is the most privacy preserving one. As Figure 3 shows, the most privacy preserving alternative is presented first. The questions and answer alternatives are as follows.

1) Who can see your data? (Vis).

• Only me (P r) • Only my friends (F ) • Everybody, even strangers on the Internet (Pu) 2) Who can receive your data? (Rec)

• Only sub-contractors of the service provider, necessary to provide service (DA) • Any third party (All) including my health insurance provider, my employer etc. 3) In what form can your data be distributed? (Form)

• Data that cannot identify me on its own (deId)

• Data that can identify me (Id) 4) How long can your data be retained? (Ret)

• One week (S)

• One year (L) Whenever the question or the answer alternatives involve term(s) that the user may be unfamiliar with, suitable but short explanations and examples are used. For example, the user may not fully understand who a "third party" is. Therefore, examples are provided to make the user aware that a third party may mean his health insurance provider or even his employer.

C. Interaction between the panes

Initially, the privacy risk pane of the screen displays the risks to the users for the default alternatives. Whenever the user inputs a preference that is different from the default option, the risk pane displays the resulting changes in the harm likelihoods.

Thus, the interactive screen allows the user to observe the impact of the change he makes in the privacy preferences on the risk level. Based on these risk levels, he can decide on the most acceptable privacy preference. After he is satisfied with his selection, he can press the "Submit" button to communicate his pereference to the service provider.

D. Links for more information

The primary or first level screen leads to several linked or second level webpages. There are four types of links, all from the privacy risk pane: 1) from the privacy harms ("Pay more health insurance premium" and "Strangers know your habits"); 2) from the likelihoods ("How likely?"); 3) from the severities ("How severe?") and 4) from the coloured buttons denoting the likelihood and severity levels. In all the second level webpages, we still retain the privacy risk pane so that the user can see the risk levels as he learns more about the different terms and colour codes. A "Back" button on the top left of these webpages allow the users to go back to the first level screen. Below, we discuss the design of the second level screens. 1) Links from privacy harms: The privacy harms on the privacy risk pane are linked to further screens that explain what these harms mean. Figure 4 shows the screen obtained by clicking the link on the text "Pay more health insurance premium" on the privacy risk pane. Each screen states the harm in a comprehensible sentence and also answers potential questions that the user may have after reading it. For example, in Figure 4, we see the explanation "Your health insurance provider may charge you more premium based on your fitness data." along with two red bubbles answering two important questions the user may ask: 1) why a health insurance provider could charge more premium based on fitness data and 2) how the health insurance provider could obtain such data.

To substantiate our claims that the harms considered are indeed legitimate scenarios and to educate the user further, we also provide links to relevant news articles at the bottom of the screens. These news articles present scenarios where such harms have occurred or may occur.

2) Links from likelihoods: The privacy risk pane shows the likelihoods of the different privacy harms. The likelihood of each harm is labelled as "How likely?" which also links to a screen that shows what leads to the current level of likelihood. Figure 5 shows this screen corresponding to the likelihood of H.1. In this screen, we highlight to the user what contributes to the likelihood of the harm, based on our analysis using the harm trees. For example, Figure 5 shows that the likelihood of the harm H.1 is only "Once in a While" mainly because of two positive (indicated by green button with "+") factors: 1) the service provider can only disclose de-identified data to his sub-contractors (since Form = deId and Rec = DA) and 2) the sub-contractors are bound legally by the service provider not to re-identify the data disclosed to them.

3) Links from severity: The privacy risk pane shows the severities of the different privacy harms. The severity of each harm is labelled as "How severe?" which also links to a screen that shows what leads to the level of severity. Figure 6 shows We assign severity values to harms based on two factors used by the CNIL [START_REF]Privacy Impact Assessment (PIA) Tools ([END_REF]: 1) how much inconveniences or difficulties are faced by the data subject and 2) whether or how easy it is for the data subject to recover from the harm. We remind the user of these two factors in a red bubble following the level of severity (see Figure 6) and explain to him our reasons for assigning a certain severity level to a harm.

If the user does not agree with the severity level assigned to a harm, he can select the severity level (from the same scale). This severity level is then displayed in the privacy risk pane.

4) Links from coloured buttons:

The coloured buttons on the privacy risk pane of the first level screen also link to another screen which explains in detail the colour scheme and the texts inside the buttons.

E. Usability features

Great care has been taken to enhance the usability of the user interface. In particular, we have: 1) Used illustrative examples and avoided the use of technical terms. 2) Presented the privacy harms in a simple language so that users can relate them to harmful consequences in their own lives. 3) Ensured readability by restricting the amount of information presented in each screen and using appropriate fonts and colours. 4) Ensured that the process of selecting privacy preferences is not confusing or too time consuming to users by including only one basic window for the purpose and limiting the number of questions and answer options. 5) Allowed users to choose the severity level of the privacy harms if they do not agree with the default choice, but kept this as an option only at a later stage to avoid confusion and too much time consumption for the average user who may just agree with the default values. 6) Presented more information through hyperlinks about the privacy harms and their severity and likelihood and the colour codes for inquisitive users who may want to educate themselves further. We have included news articles related to each privacy harm so that users can refer to them to improve their awareness. 7) Kept the default privacy preference to be the most privacy preserving one, so that users who skip this selection step can still benefit from the highest level of privacy ("privacy by default" principle).

V. RISK ANALYSIS WITH PRIVACY PARAMETERS

In Section IV, we presented the interactions with users to allow them express their privacy preferences and to inform them about privacy risks, but without explaining the actual computation of these risks. Here, we focus on the risk analysis itself, based on the methodology introduced in [9], [START_REF] De | Privacy Harm Analysis: A Case Study on Smart Grids[END_REF], enhanced with facilities to deal with privacy parameters. The primary objective of a risk analysis is to identify the privacy harms for a system in a given context and to assess the associated risks, generally measured in terms of likelihood and severity.

Several factors can influence the likelihoods of the privacy harms. The exploitability of personal data can be characterized by the resources (e.g., technical resources, access rights, background knowledge) needed by a risk source to exploit them. The dual notion is the capacity of a risk source which is defined by its resources (e.g., technical resources, access rights, background knowledge). The motivation represents the incentives and disincentives of a risk source to cause a feared event or a harm. The values of the privacy parameters influence the values of exploitability of data, the capacity and the motivation of risk sources in certain cases. In the next subsections, we study this influence and show how it can be taken into account in the privacy risk analysis process.

A. Exploitability of Data

Some data may be accessible to certain risk sources legitimately. It may be either because the risk source controls a component storing or processing the data or because the risk source has legitimate access rights to the data (e.g., when Vis = F ). The control over data allows a risk source to use that data in any way. In our case study, the service provider (A.1) has full control over the database server (DS) and the application server (AS) and hence can access all necessary data in these components without attacking them or UA.

Risk sources that have no control over a piece of data have to exploit (or attack) it, persistently or transiently. To this aim, they need resources that may or may not be available to them. By transient exploitation, we mean an exploitation for a short period of time or infrequent exploitation; by persistant exploitation we mean an exploitation for a long period of time (e.g., for several days or months). When the retention duration of a data is long, i.e., a year (Ret = L), it becomes vulnerable to transient exploitation. In contrast, if the retention duration is short, i.e., a week (Ret = S), it is only vulnerable to persistant exploitation. For example, data (such as edf it i and pdf it i ), if retained for a short duration in DS or in UA, require persistant exploitation. On the other hand, when retained for a long duration, transient exploitation is sufficient. We assume that data is stored in AS and TD for a short time. Hence, these data require persistant exploitation.

Cryptographic keys and passwords are securely stored by the service provider. So, control on the component storing them (DS) is required to exploit them (this is the highest level of protection or the lowest level of exploitability). We also assume that the service provider has taken enough measures to prevent the disclosure of passwords through UA. So, control is required to exploit password-protected data by obtaining pwd i from UA.

The exploitability values of the different data types for different components and for different retention durations are shown in Table I 4 . The exploitability values that are not affected by retention durations are shown in Table II.

Background information is not a part of the data stored in the system. So, it does not have any exploitability value.

B. Capacity and Motivation of Risk Sources

A risk source can possess the capacity for transient or persistant exploitation or may control one or more data elements or one or more components. The highest capacity of any risk source with respect to a data element or a component is to have control over that data element or component. For example, the service provider (A.1) controls AS and DS. of any risk source is the inability to perform any exploitation as in the case of the user's friend (A.2) when Vis = P r. A.3 and A.5 have persistant and transient capacities respectively.

The control over data can be influenced by the value of visibility. For example, under the default value for visibility (i.e., Vis = P r), a friend (A.2) of the user or the public (A.4) have no control over any data and no technical resources to exploit them. However, when the user allows his data to be visible to his friends (i.e., Vis = F ), they gain control over this data (similarly for the public in general when Vis = P u).

The availability of background information to some risk sources is also considered as a part of their capacity. We consider that a risk source has a "high" capacity if it possesses the background information relevant for an exploitation, and "low" otherwise. The only background information considered here is ID i . As shown in Figure 1,A.5 must be able to exploit df it i , f it i and/or loc i which can be provided by A.1 in deidentified form. We assume that A.5 has a "low" chance of possessing this background information.

The privacy parameters recipients and form influence the value of the motivation of the service provider (A.1) to perform an exploitation. We assume that the motivation of the service provider to comply with the privacy settings of the user is always "high". If the user specifies a less privacy preserving option, then the motivation of the service provider to choose the option which gives him more incentive is always "high" and that of the option which gives him less incentive is "low". For example, the motivation of the service provider to disclose identified data is "low" when the user limits this disclosure to de-identified data, due to the fear of legal sanctions and the loss of consumer trust. Otherwise, the motivation of disclosing identified data is "high" due to financial incentives.

For other risk sources, the motivations (see Table III) are not affected by the privacy parameters. The motivation of a friend (A.2) to access (FE.3) and disclose the user's personal data (FE.2) when it is legitimately accessible to him (i.e., Vis = F ) is "medium" because such an access is generally easy but these actions may lead to embarrassments. On the other hand, the motivation for a friend (A.2) to access (FE.3) and disclose personal data (FE.2) through an attack to know the password (A.2 is not a hacker) is "low" because it may lead to loss of friendships. Hackers, on the contrary, have a "high" motivation to access (FE.3) and disclose (FE.2) any data. Any other member of the public (A.4) has a "medium" motivation to access the user data (FE.3) (they may seek quick monetary gains, but also fear getting caught). Third parties, other than sub-contractors of the service provider, have a "high" motivation (considering worst case) to disclose and use data for unauthorized purposes (FE.2, FE.1) and to make use of any identifying information (ID) available to them as background information. Sub-contractors of the service provider, however, have "low" motivation as they are legally bound by the service provider not to disclose, misuse or reidentify data disclosed to them by the service provider. Some combinations of feared events and risk sources do not make sense. The corresponding rows are marked with '×' in Table III. For example, the friends (A.2) of the user are not given access to data for any particular purpose.

Similarly, the public (A.4) is not provided access to data with any specific purpose nor is there any intention of the user to hide some data when he allows its disclosure to the public. Third parties (A.5) do not perform unintended access to data (FE.3) because this would qualify them as hackers (A.3).

The motivation of business partners of the service provider (A.5) to use background information is "high" due to potential financial incentives.

C. Computation of Likelihoods

The computation of the likelihoods of the harms based on the harm trees shown in Section II-F can be carried out in two steps. The first step is the assessment of the likelihoods of the leaves of the harm trees (likelihood of exploitation of personal data) from the motivation and the capability of the relevant risk sources using Table IV. The capability of the risk source to perform an exploitation is derived by comparing the value of the exploitability of the data and the capacity of the risk source. A risk source has a "high" capability when its capacity satisfies the desired conditions (w.r.t. control, persistant and transient access) for exploitability, otherwise it has a "low" capability. This assessment is based on Section V-A and Section V-B. To be consistent with other leaf nodes, the leaf nodes corresponding to background information (for which there are no exploitability) are directly assigned a likelihood value based on a "high" capability (since background information, when available, is easily usable by risk sources) and the motivation of the risk source to use it. The second step is the computation of the likelihood of each harm according to the following rules (applied bottom-up), where P i is the likelihood of the ith child node: R1) AND node with independent child nodes: i P i . R2) AND node with dependent child nodes5 : M in(P i ), R3) OR node with independent child nodes: 1i (1 -P i ). R4) OR node with dependent child nodes6 : M in(1, i P i ).

To perform the computations of the second step, it is necessary to translate the symbolic likelihood values of Table IV into numerical values. This transformation has to be made by the privacy expert in collaboration with the owner and should be documented. In this paper, we use as an illustration the following correspondance for the likelihood values (p): 1) Negligible (N): p < 0.01%; 2) Limited (L): 0.01% ≤ p < 0.1%; 3) Intermediate (I): 0.1% ≤ p < 1%; 4) Significant (S): 1% ≤ p < 10%; 5) Maximum (M): p ≥ 10%.

D. Choice of Privacy Preferences

Table VI shows that the default user setting leads to the lowest level of risk, i.e., the likelihoods of both H.1 and H.2 are "intermediate". We also observe that changing the default values of Ret to L does not increase harms (i.e., their likelihood values remain unchanged). Changing the default values of Rec to All or Vis to P u or Form to Id make the harms riskier (i.e., their likelihood values increase).

The results of the previous sections can help the user to decide upon an acceptable likelihood for each harm, given their severity. Based on Table VI, and the acceptable threshold, he can then decide which values for the privacy parameters he prefers. Let us assume that the user decides that the acceptability threshold for a harm with "very bad" severity (for example H.2) is "intermediate" and that of a harm with "bad" severity (for example, H.1) is "significant". Then, he may choose any privacy preference (from Table VI) other than the ones in which Vis = F or Vis = P u.

Table V shows how the colour coding and the texts used in the screens for "How likely?" in Section IV map to the scale for likelihood used in Section V.

VI. RELATED WORKS

The communication of privacy policies to users in a comprehensible form has been an important focus of privacy [START_REF] Roy | Terms of Service Didn't Read[END_REF] aims to classify, through a transparent and peer-reviewed process, the terms of service and the privacy policies into six colour-coded classes. Privacy icons [START_REF] Holtz | Towards Displaying Privacy Information with Icons[END_REF] or privacy policy icons [START_REF] Fischer-Hübner | How Can Cloud Users be Supported in Deciding on, Tracking and Controlling How their Data are Used?[END_REF] are simplified pictures used to visualize elements of privacy policies. Inspired by nutrition labeling etc., Kelley et al. [START_REF] Kelley | A Nutrition Label for Privacy[END_REF], [START_REF] Kelley | Standardizing Privacy Notices: An Online Study of the Nutrition Label Approach[END_REF] propose the privacy nutrition label to improve the accessibility, readability and understanding of privacy policies among users.

Poor, confusing interface design, permissive default settings, limited visual feedback etc. can often lead to the underutilization of available privacy options [START_REF] Gross | Information Revelation and Privacy in Online Social Networks[END_REF], [START_REF] Lipford | Understanding privacy settings in facebook with an audience view[END_REF].

Different types of Transparency Enhancing Tools (TETs) have also been proposed to allow users to express their privacy choices or to inform them about the privacy policies of service providers. PrivacyBird [1] can compare user privacy preferences with P3P policies and help the user decide whether to reveal data to the website [START_REF] Cranor | User Interfaces for Privacy Agents[END_REF]. Other similar TETs provide insight about the privacy implications of potential or past data disclosures (Mozilla Privacy Icons [2], PrimeLife's Privacy Dashboard [3], Google Dashboard [4], Privacyscore [START_REF] Janic | Transparency Enhancing Tools (TETs): An Overview[END_REF]). Still others provide insights into third party tracking (Lightbeam [5]) or promote privacy awareness and education about privacy problems among users and (Me & My Shadow [6]). The work described in this paper is complementary to the above proposals. Unlike previous work in this area, our objective is to help users in the definition of their privacy settings, based on a privacy risk analysis. It is also complementary to previous papers by the authors [START_REF] De | PRIAM: A Privacy Risk Analysis Methodology[END_REF], [START_REF] De | Privacy Harm Analysis: A Case Study on Smart Grids[END_REF] which introduced a methodology for privacy risk analysis and its application to smart metering but did not address the use of privacy risk analysis to enable informed privacy settings.

VII. CONCLUSIONS AND FUTURE DIRECTIONS

The concepts presented in this paper can form the basis of a full fledged privacy tool enabling data subjects to make informed choices about their privacy settings. It could also form the core of an education tool to increase awareness about privacy [START_REF] Schaub | A Design Space for Effective Privacy Notices[END_REF]. An avenue for further research is the extension to dynamic risk analysis to take into account the personal data disclosure history of the user. It would be useful, for example, to analyze the impact on privacy risks of the disclosure of new personal data to a third party that has already collected data on the subject. Another interesting research direction is the integration of alternative actions (such as disclosure of anonymized data, less precise data, or even fake data) and their consequences. A better understanding of these options would further enhance the control of individuals on their personal data.

  Fig. 1. Harm tree for "increased health insurance premium" (H.1)

Fig. 3 .

 3 Fig. 3. First level screen showing the default user privacy preference (Ret = S) ∧ (Rec = DA) ∧ (Vis = P r) ∧ (Form = deId) and its risks

Fig. 4 .

 4 Fig. 4. Second level screen linked from the harm "Pay more health insurance premium" for the user privacy preference (Ret = S)∧(Rec = DA)∧(Vis = F ) ∧ (Form = deId)

Fig. 5 .

 5 Fig. 5. Second level screen linked from "How likely?" for H.1 for the user privacy preference (Ret = S)∧(Rec = DA)∧(Vis = F )∧(Form = deId)

  S) ∧ (Rec = DA) ∧ (Vis = P r) ∧ (Form = deId) (Default preference) Intermediate Intermediate (Ret = L) ∧ (Rec = DA) ∧ (Vis = P r) ∧ (Form = deId) Intermediate Intermediate (Ret = S) ∧ (Rec = All) ∧ (Vis = P r) ∧ (Form = deId) Significant Intermediate (Ret = S) ∧ (Rec = DA) ∧ (Vis = F ) ∧ (Form = deId) Intermediate Significant (Ret = S) ∧ (Rec = DA) ∧ (Vis = P u) ∧ (Form = deId) Intermediate Significant (Ret = S)∧(Rec = DA)∧(Vis = P r)∧(Form = Id) Significant Intermediate (Ret = S)∧(Rec = All)∧(Vis = P r)∧(Form = Id) Significant Intermediate

  The least capacity

	Compo-nent UA	UPref × (irrespective of retention time)	Data df iti, f iti, loci	Exploitability Control
	DS	× (irrespective of retention time)	k, k , pwdi	Control
	UA	× (no retention time)	pwdi	Control
			TABLE II
	EXPLOITABILITY VALUES OF DATA NOT AFFECTED BY RETENTION (RET)

TABLE VI SUMMARY

 VI OF HARM LIKELIHOODS FOR DIFFERENT USER PREFERENCES research. The ToS;DR project

For example, Recital 7 states that "Natural persons should have control of their own personal data".

For example, Recital

states that "Natural persons should be made aware of risks, rules, safeguards and rights in relation to the processing of personal data and how to exercise their rights in relation to such processing."

Other risk sources such as governments could also be considered but they are not discussed here for the sake of conciseness.

In TableI, the exploitability value of data stored in TD or in AS are affected by the retention time. However, in our case, we have assumed that the service provider has reasonably decided to store the data in these components for a short duration. If he had made the other choice or different choices for these two components, the exploitability values would have been different.

In order to err on the safe side in terms of privacy protection, we consider dependent nodes such that one node may imply the other nodes.

In order to err on the safe side in terms of privacy protection, we consider dependent nodes such that each node may exclude the other nodes.

VIII. ACKNOWLEDGEMENTS

This work has been partially funded by the CHIST-ERA project UPRISE-IoT.