Tuong-Bach Nguyen
email: tuong-bach.nguyen@gipsa-lab.grenoble-inp.fr

Isabelle Sivignon
email: isabelle.sivignon@gipsa-lab.grenoble-inp.fr

Epsilon-covering: a greedy optimal algorithm for simple shapes

Unions of balls are widely used shape representations. Given a shape, computing a union of balls that is both accurate in some sense and of small cardinality is thus a challenging problem. In this work, accuracy is ensured by imposing that the union of balls, called covering, is included in the shape and covers a parameterized core set (namely the erosion) of the shape. For a family of simple shapes, we propose a polynomial-time greedy algorithm that computes a covering of minimum cardinality for a given shape.

Introduction

Unions of balls are common shape representations, useful for instance to describe molecules in biochemistry [START_REF] Cazals | Greedy geometric algorithms for collection of balls, with applications to geometric approximation and molecular coarsegraining[END_REF], to quickly detect collisions [START_REF] Bradshaw | Adaptive medial-axis approximation for sphere-tree construction[END_REF] between shapes or to derive higher-level representations. The ubiquity of unions of balls is largely due to the existence of provably good conversion algorithms that allow us to derive them from various representations such as point clouds and polygonal meshes [START_REF] Miklos | Discrete scale axis representations for 3d geometry[END_REF]. However, the union of balls output by the conversion process provides only an approximation of the original shape.

In a previous work [START_REF] Attali | Epsiloncovering is NP-complete[END_REF], we introduced a novel way, called ε-covering, of controlling the geometric error between a given input shape and a selected union of balls. The idea is to impose that the union of balls covers a core set of the shape and does not cross over an outer set. This problem falls in the family of geometric set cover problems, where the goal is to minimize the number of balls. We proved that, in the general case, computing an ε-covering of minimum cardinality is an NP-complete problem. Other approaches, related to the maximum kcover problem, aim at maximising the coverage for a fixed number of balls [START_REF] Cazals | Greedy geometric algorithms for collection of balls, with applications to geometric approximation and molecular coarsegraining[END_REF], but the problem is also NPcomplete.

In this work, we consider the family of input shapes that are themselves 2D unions of balls with a tree-like structure. An ε-covering of such a shape is a simplified union of balls. We present a polynomial-time algorithm that computes an ε-covering of minimum cardinality for this specific family. To do so, we rely on the medial axis structure of unions of balls, and show how to continuously sweep its pencils in order to get a correct and optimal result.

Statement of the result

In this paper, R 2 is endowed with the Euclidean distance. For any point c and real r > 0, we denote by b(c, r) the closed ball of center c and radius r. For any subset S ⊆ R 2 , we respectively denote its closure, interior, complement, boundary, and medial axis by S, S, S c , ∂S, and MA (S). Let ε > 0 be a real number. The erosion of S (by ε) is S ε = {y | b(y, ε) ⊆ S}. For any collection of balls B, we write B = ∪ b∈B b.

Definition 1 An (inner) ε-covering of S is a collection of balls B such that S ε ⊆ B ⊆ S.

For given S and ε, there exist many ε-coverings of S, with different cardinalities. We say that an ε-covering is optimal if it achieves minimum cardinality. In general, finding such an optimal ε-covering for S is an NP-complete problem [START_REF] Attali | Epsiloncovering is NP-complete[END_REF], but we focus here on simple shapes S and prove the following result:

Theorem 1 There is a polynomial-time algorithm to compute optimal ε-coverings for finite unions of balls whose medial axis is cycle-free.

In Section 3, we present some results on the structure of unions of balls, before describing the principle of our algorithm in Section 4. Section 5 expands on some practical considerations required for the algorithm, and Section 6 is dedicated to proving that it indeed achieves the claimed result.

Union of balls

Medial axis and pencils

In order to specify our algorithm, we must elaborate on the structure of unions of balls, in particular that of their medial axis. Recall that a ball b ⊆ S is a medial ball if its boundary ∂b intersects ∂S at least twice. The medial axis MA (S) is the collection of the centers of these medial balls. Owing to the structure theorem of the medial axis of a union of balls [START_REF] Amenta | The medial axis of a union of balls[END_REF], we know that for a finite union of balls S, MA (S) is a finite collection of line segments. We also know that each of these line segments coincides with a pencil of balls [START_REF] Cazals | Greedy geometric algorithms for collection of balls, with applications to geometric approximation and molecular coarsegraining[END_REF] in the following sense.

Borrowing the terminology used in [START_REF] Schwerdtfeger | Geometry of complex numbers: circle geometry, Moebius transformation, non-euclidean geometry[END_REF], an elliptic pencil can be characterized by two points u, v ∈ R 2 : it is the family of all balls whose boundary goes through u and v. The collection of their centers forms a line. In this paper, we only manipulate elliptic pencil segments, that are subsets of elliptic pencils whose collection of centers forms a segment instead of a line. From here on, we will not consider any proper line pencil, and thus we refer to these elliptic pencil segments simply as pencils. As such, the pencils we consider always have two endpoint balls b 1 and b 2 . We denote the pencil they generate by [b 1 b 2 ]. A basic property of a pencil is that the domain it covers, that is the collection of all points covered by some ball of the pencil, is the union of b 1 and b

2 , [b 1 b 2 ] = b 1 ∪b 2 .
Linking back to the previous remark, MA (S) is a collection of pencils. Indeed, for each segment of the medial axis, there are two points u, v ∈ ∂S, such that any medial ball centered at a point of that segment contains both u and v in its boundary. Thus, each segment of MA (S) coincides with a pencil. Hence a union of balls can always be interpreted as a union of pencil domains (see Figure 1 for an illustration).

The medial axis of a closed shape and its erosion always satisfy the below inclusion.

Proposition 2 MA (S ε ) ⊆ MA (S) Proof. Consider c ∈ MA (S ε ) and b = b(c, r) ⊆ S ε medial in S ε . Let b + = b(c, r + ε).
We prove that b + is medial in S which implies that c ∈ MA (S). First, note that b + = ∪ y∈b b(y, ε) ⊆ S, hence if ∂b + intersects ∂S at least twice, it is medial in S. By definition of b, there are at least two points u = v in the intersection of ∂b and ∂ (S ε ). Since u, v ∈ ∂ (S ε ), there are u

+ , v + ∈ ∂S such that u -u + = ε = v -v + . By triangular inequality we have c -u + ≤ c -u + u -u + = r + ε, hence u + ∈ b + . Since u + ∈ ∂S, nec- essarily u + /
∈ b and we have c -u + ≥ r+ε. Therefore c -u + = r + ε, thus u + ∈ ∂b + ∩ ∂S. Also, we have equality in a triangular equality, hence c, u and u + are aligned. Likewise, v + ∈ ∂b + ∩ ∂S, and c, v and v + are also aligned. Thus, if u + = v + , then b + is medial in S. By contradiction, assume that we have u + = v + . Then, c, u, v and u + must be aligned. Because u = v, we have the below situation.

c u v u + r r ε Hence v -v + = v -u + = 2r + ε = ε. This implies r = 0 and u = v, which is impossible. Therefore, u + = v + and b + is medial in S.
Thus for unions of balls, MA (S ε ) splits MA (S) into two finite collections of line segments: segments that are part of both MA (S) and MA (S ε ), and segments that are exclusively part of MA (S). We respectively refer to them as eroded and non-eroded pencils.

Partial ordering on medial balls

MA (S) being a collection of segments, it can be viewed as the embedding of a graph in R 2 . By assumption on the class of shapes considered, MA (S) is cycle-free, hence it is a forest. Since we can process each tree of the forest independently, we assume without loss of generality that MA (S) is a tree. By picking any point x of MA (S) as a root, we obtain an orientation of MA (S) which induces a partial order on MA (S). Indeed, we simply have to orient all the edges of MA (S) from the leaves to the root x. We denote by T the resulting oriented tree. The structure represented by T is at times called anti-arborescence or in-tree, and can also be viewed as a directed acyclic graph with a unique sink. For any y, z ∈ MA (S), we say that y is T -smaller than or equal to z, and note y ≤ T z, if z belongs to the unique path from y to the root x of T . We also use the usual order symbols and notions such as being T -larger or equal to, ≥ T , or also being strictly T -smaller, < T . Note that this T -order is valid for all points of MA (S), and not simply vertices of T . Because points of MA (S) are centers of medial balls of S and S ε , this T -order extends to medial balls. Specifically, we can Tcompare two medial balls of either S or S ε , but also a medial ball of S with a medial ball of S ε .

Since T only induces a partial order, we say that two balls that cannot be ordered by T are T -unrelated. . By convention, if c is not a vertex of T but an inner edge point, we say that c has degree 2. We denote the degree by deg (c).

Algorithm

Principle

For our proposed algorithm, the partial ordering we introduced allows the definition of clear start and end points, as well as a measure of progress. Indeed, let b 0 = b(c 0 , r 0 ) be a medial ball of S. Its center c 0 splits MA (S) into deg (c 0 ) connected components. We denote these components by branch (c 0 , i), 1 ≤ i ≤ deg (c 0 ). For our purpose, we want to express the domain covered by balls centered at points of these components of MA (S), but not covered by b 0 . First we define the collection of related medial balls, (see Figure 1). As for the later domains, we refer to their union as the T -small component and note C(b 0 , -). Hence, we have

C (b 0 , i) = {b(c, r) medial in S | c ∈ branch (c 0 , i)}. Then the do- main of each C (b 0 , i) is C(b 0 , i) = C (b 0 , i) \ b 0 . With these notations, b 0 also splits S into the different C(b 0 , i)'s,
S \ b 0 = C(b 0 , +) ∪ C(b 0 , -).
From the definition, we also deduce the following:

Proposition 3 If b 1 ≤ T b 2 , then C(b 1 , -) ⊆ C(b 2 , -) and C(b 1 , +) ⊇ C(b 2 , +).
Now assume we want to traverse and sweep S with a medial ball, starting from a leaf of T , toward its root. When we reach a medial ball b 0 , then at that moment, C(b 0 , -) ∪ b 0 corresponds to the domain of S that was swept by our medial ball, and C(b 0 , +) to the domain of S that was not swept by it. Our approach is based on this particular decomposition of S. We want to use a greedy approach to iteratively compute an ε-covering of the T -small component C(b 0 , -). Because T may have several leaves, it is necessary to extend the above definitions of T -small and T -large components to collections B of medial balls, while preserving the interpretation that C(B, -) ∪ ( B) is the domain of S already processed, and C(B, +) is the domain of S that has not been processed yet. The domain already processed for a collection of balls should thus be the union of the domains already processed by some To formalize the procedure presented above, we require two more definitions.

b ∈ B. Hence the T -small component of B is C(B, -) = ∪ b∈B C(b, -).
Definition 2 Let B be a collection of medial balls in S. We say that B is a

T -small ε-covering of S if it covers S ε in its T -small component C(B, -), that is if C(B, -) ∩ S ε ⊆ B.
Note that every ε-covering is also a T -small ε-covering of S. As such, we employ the term partial T -small ε-covering if we need to distinguish from complete εcoverings.

Definition 3 Let B be a partial T -small ε-covering of S, and b 0 be medial in S. We say that b 0 is a candidate ball with respect to B, if

B 0 = B∪{b 0 } is also a T -small ε-covering of S, and S ε \ B 0 S ε \ B. The strict inclusion S ε \ B 0 S ε \ B ensures that B 0 is closer to being a complete ε-covering than B.
Hence, for any partial T -small ε-covering, iteratively adding a candidate to the collection ensure that at some point we will obtain a complete ε-covering. Because any partial T -small ε-covering always have an infinity of candidates, we elect to add only T -maximal candidates, that is T -maximal among the collection of candidates.

Specification

Our algorithm is based on a loop over the collection of all eroded and non-eroded pencils of MA (S) in a topological order. Since MA (S ε ) ⊆ MA (S), we can simultaneously sweep S and S ε . With our partial ordering on MA (S), a topological order of its vertices (v 1 , . . . , v n+1 ) is such that for i ≤ j, then either v i ≤ T v j , or v i and v j are T -unrelated. Besides the root, each vertex is incident to exactly one pencil composed of T -larger points of MA (S), hence any topological ordering of vertices induces an ordering of pencils

([v 1 v 1 ], . . . , [v n v n ])
, where v i ∈ {v 1 , . . . , v n }. This ordering of pencils thus satisfies that for i < j, then either

v i < T v i ≤ T v j < T v j , or v i and v j are T -unrelated.
As we loop over the pencils, we maintain a collection of medial balls B which is a T -small ε-covering, while looking for T -maximal candidates to add to said collection. When we process a pencil, we compute a collection of constraints to pass on to the next incident pencil. A constraint is a point or circular arc that any ball T -larger than the pencil (that is T -larger than any ball of that pencil) must contain in order to be a candidate for B. Hence, if no T -maximal candidate is found in the currently processed pencil, the set of constraints it will pass on to its incident T -larger pencil is the collection of all constraints it itself inherited from incident T -smaller pencils, plus new constraints specific to the current pencil. Then, we can compute the T -maximal ball that contains all these constraints. If it is not the T -large endpoint of the pencil, we call it critical. We claim that for well chosen constraints, critical balls are T -maximal candidates. The overall approach is summed up in Algorithm 1. Retrieve incident constraints

5:

Search for a critical ball in the pencil

6:

If a critical ball b is found then

7: B ← B ∪ {b} 8:
end If

9:

Compute the constraints to pass on 10: end Loop 11: Return B (a) All that remains is to explicit constraints which guarantee that critical balls are indeed T -maximal candidates. Consider a candidate b 0 to the collection B. We can ignore balls which are T -unrelated to b 0 , thus let

x S ε ε c0 b0 C(b0, -) b1 b2 C(B, -) (b) x c0 x c 0 A \ X v
B = {b ∈ B, b ≤ T b 0 }. By definition, B 0 = B ∪ {b 0 } is a T -small ε-covering. The domain of S ε covered by C(B 0 , -) ∪ ( B 0 ) but not by C(B , -) is contained in ( B 0 ) \ C(B , -). Let that former domain be A = ÄÄ C(B 0 , -) ∪ Ä B 0 ää \ C (B , -) ä ∩ S ε = ((C(b 0 , -) ∪ b 0 ) \ C(B , -)) ∩ S ε
and the latter be

X = Ä B 0 ä \ C(B , -) = b 0 ∪ Ä T -max (B ) ä .
See Figure 2a. A and X both vary depending on B and b 0 , and in light of the previous remark, b 0 is a candidate to B if and only if A ⊆ X. Explicitly ensuring and verifying that we indeed have the inclusion A ⊆ X is non trivial. Instead, we claim that it is sufficient to ensure the two conditions:

(i) ∂A ⊆ X,

(ii) ∀ vertex v ∈ ∂X, ∃N v an open neighbourhood of v, such that N v ∩ A ⊆ X.
Note that both ∂A and ∂X are finite collections of circular arcs, whose intersections we call vertices of the boundary. Since these boundaries have a finite combinatorial structure, (i) and (ii) are more readily verifiable and can be enforced. Also, as illustrated in Figure 2b, condition (i) by itself is insufficient to ensure that b 0 is a valid candidate. We take as constraints for Algorithm 1 any arc of ∂A not in B , as well as any vertex of ∂ ( T -max (B )) whose neighbourhood in A is not fully contained in B . This ensures that critical balls can be computed as per Section 5 and fulfill conditions (i) and (ii). Both conditions are necessary to have the inclusion A ⊆ X. We prove in Section 6 that they are also sufficient.

Computation of critical balls

As stated previously, each pencil inherits a collection of constraints that are either a singleton point or a circular arc. Because of Proposition 4, which will be stated and explained in detail later, when we sweep a pencil from an endpoint to the other, a point that exited the sweep ball will never re-enter it, and a point that entered the sweep ball will never exit it. Thus, to each constraint corresponds a single-constraint critical ball b crit : any ball strictly T -larger than b crit cannot fully contain the constraint, hence cannot be a candidate, while any ball T -smaller than or equal to b crit will always contain the constraint and may be a candidate. Therefore, the critical ball for the overall collection of constraints is the T -maximal ball that is T -smaller than all single-constraint critical balls, that is the unique Tminimal ball amongst all single-constraint critical balls.

From here on, we omit the qualifier "single-constraint". Also, because we parameterize balls of a pencil by an interpolation value λ, we call critical λ an interpolation value which corresponds to a critical ball.

The next sections present how to compute a critical ball given a single constraint. Section 5.1 presents a very useful property of pencils and how to handle point constraints, while Section 5.2 deals with arc constraints. The power of a point with respect to balls of the pencil is thus linear in λ and may only change sign once. This justifies our earlier claim that when sweeping a pencil, a point can exit or enter the sweep ball only once.

Point inclusion

Proof. By definition, all the balls of a pencil [b 1 b 2 ] share exactly two points {u, v} = ∂b 1 ∩ ∂b 2 on their boundary. We have r 2 λ = u -c λ 2 . Hence:

pow (y, b λ ) = y -c λ 2 -u -c λ 2 = y 2 -2 c λ , y + c λ 2 - Ä u 2 -2 c λ , u + c λ 2 ä = 2 c λ , u -y + y 2 -u 2
Note that this identity also holds for b 1 and b 2 since they coincide with b λ , for λ ∈ {0, 1}.

pow (y, b λ ) = 2 λc 1 + (1 -λ) c 2 , u -y + y 2 -u 2 = λ Ä 2 c 1 , u -y + y 2 -u 2 ä + (1 -λ) Ä 2 c 2 , u -y + y 2 -u 2 ä = λ pow (y, b 1 ) + (1 -λ) pow (y, b 2 )
This proof actually extends to all balls of the complete line pencil. From there, given two endpoint balls of a segment pencil and a single constraint point, we can easily compute the value λ crit for which b λcrit will be critical. From the design of Algorithm 1, and assuming that b 1 ≤ T b 2 , we will always have λ crit ≥ 0. If we happen to have λ crit > 1, then the segment pencil does not contain any critical ball for that constraint point, since all balls of the pencil contain that constraint point.

Arc inclusion

For arc constraints, we use the same approach of computing a critical value for λ. If all of these critical λ's are strictly larger than 1, then the pencil does not contain any T -maximal candidate. If any are less than or equal to 1, then the minimum value yields a T -maximal candidate. All that remains is thus being able to compute such a critical λ for arc constraints. To do so, we first need to compute this critical value for a ball.

Critical λ for balls

Consider a constraint ball b = b(c, r). We want to compute the critical values of λ for which b is fully contained in b λ . Hence:

b ⊆ b λ ⇐⇒ r λ ≥ c -c λ + r ⇐⇒ r 2 λ ≥ c -c λ 2 + r 2 + 2r c -c λ ⇐⇒ - Ä c -c λ 2 -r 2 λ ä -r 2 ≥ 2r c -c λ ⇐⇒ -pow (c, b λ ) -r 2 ≥ 2r c -c λ ⇐⇒ -pow (c, b λ ) -r 2 2 ≥ 4r 2 c -c λ 2 & -pow (c, b λ ) -r 2 ≥ 0
Since pow (c 0 , b λ ) is linear in λ as per Proposition 4, we introduce two constants A and B such that Aλ + B = pow (c, b λ ) + r 2 to simplify notations. We have

A = pow (c, b 1 ) -pow (c, b 2 ) B = pow (c, b 2 ) + r 2 .
We focus on the first inequality, (Aλ + B)

2 ≥ 4r 2 c -c λ 2 .
For the right hand side, the factor c -c λ 2 can be developed as follows

c λ -c 2 = λ (c 1 -c 2 ) + c 2 -c 2 = λ 2 c 1 -c 2 2 + 2λ c 1 -c 2 , c 2 -c + c 2 -c 2 and thus, it is quadratic in λ. Therefore b ⊆ b λ ⇐⇒ Cλ 2 + Dλ + E ≥ 0 & Aλ + B ≤ 0 where C = A 2 -4r 2 c 1 -c 2 2 D = 2AB -8r 2 c 1 -c 2 , c 2 -c E = B 2 -4r 2 c 2 -c 2
A, B, C, D and E are constant with respect to λ and thus the inclusion test can be reduced to a sign analysis of polynomials of degree 2 and 1. From the roots of these polynomials, we can thus derive the critical values of λ.

Critical λ for arcs

In order to compute the critical λ value for an arc constraint e, we first require the critical value for the ball b supporting that arc, that is the ball such that e ⊆ ∂b.

Let λ be the critical value for that supporting ball.

With λ , we can then compute the tangency point y between b and b λ . This particular point, in addition with the endpoints of arc e, are sufficient to compute the critical value of e. Indeed, for λ ≤ λ , the whole ball b is contained in b λ , hence we also have e ⊆ b λ . For λ > λ , two cases arise. Either y ∈ e or y / ∈ e. In the former, we have y ∈ e \ b λ hence the critical value for the arc e is In the former, we have y ∈ e and y / ∈ b λ hence the critical value for the arc e is λ itself. In the latter, note that b λ splits ∂b into two connected components, one which is inside b λ , and the other outside. By Proposition 4, the outside component will always contain y. For λ > λ crit , any point of e not in b λ must be path-connected in ∂b to y. Therefore, some endpoint of e also belongs to the outside connected component. It immediately follows that if both endpoints of e actually belong to b λ , then the whole arc e is also contained in b λ . Therefore, the critical value for e is in this case equal to the smallest critical value of its endpoints. Proof. Let A and X be defined from b 0 and B. Consider H = A \ X = A ∩ X c . By contradiction assume that H = ∅. First, notice that ∂H ⊆ ∂X. Indeed,

∂H = ∂(A ∩ X c ) ⊆ ∂A ∩ X c ∪ ∂ (X c ) ∩ A . By con- dition (i), ∂A ⊆ X and we have ∂A ∩ X c ⊆ ∂X. Also, ∂ (X c ) = ∂X. Hence ∂H ⊆ ∂X. Let H i be a connected component of H. Since ∂H i ⊆ ∂H, hence ∂H i ⊆ ∂X. We have H i ⊆ X c connected, with ∂H i ⊆ ∂X. Thus, H i is actually a connected component of X c . H i being bounded, it is commonly called a hole of X. As a hole of X, any vertex of ∂H i is also a vertex of ∂X. Let v be a vertex of ∂H i . For all open neighbourhood N v of v, we have N v ∩ H = ∅. Since H = A ∩ X c , we deduce ∅ = N v ∩ A X.
This contradicts (ii) and is impossible. Therefore, H = ∅, A ⊆ X, and b 0 is indeed a candidate for B.

From the above lemma, Algorithm 1 indeed finds candidates and eventually converges to an ε-covering. We now show that it converges in polynomial time.

ities C(B 0 , -) \ C(B, -) = C(b 0 , -) \ C(b, -) = b \ b 0 . Hence, we obtain A = ((b \ b 0 ) ∪ b 0 ) ∩ S ε ⊆ b ∪ b 0 , thus b 0 is a candidate for B. Therefore, |B algo | ≤ 2n.
We now analyse the complexity. Computing a topological ordering [START_REF] Cormen | Introduction to Algorithms[END_REF] is linear in n. Enforcing a single constraint takes constant time (see Section 5), hence the time expanded to search for a critical ball depends on the number of constraints. This number cannot exceed the combinatorial complexity of the boundaries of S ε and B algo . The former is linear in n. As for the latter, it is linear in the size of B algo , which is itself linear in n. Thus, Algorithm 1 is quadratic in n.

Convergence to an optimal solution

In order to prove that our algorithm reaches an optimal, we rely on several intermediate results. We introduce a sequence of three lemmas, the last of which we reformulate, through two corollaries, in terms of candidate ball to a partial T -small ε-covering. Then, we finally prove Proposition 12. Lemma 8 Consider a finite union of balls S such that MA (S) is a tree. Then S c is path-connected.

Proof. Let S be the collection of medial balls in S which are centered at a vertex of MA (S). S has finite cardinality and we have S = S. We proceed by induction on n = |S |, and henceforth use the notation S n = S n for collection of balls with cardinality n. For n = 1, S 1 is only a ball, the property is verified. Now consider a collection S n+1 , and let b ∈ S n+1 such that b is centered on a leaf of MA (S n+1 ). Let S n = S n+1 \{b} and S n = S n .

Using Lemma 7, we deduce that S c n+1 = S c n ∩ b c . Consider y, z ∈ S c n+1 . By induction assumption, we know that S c n is path-connected, hence there is a path γ ⊆ S c n connecting y and z. We build from γ another path γ ⊆ S c n+1 that connects y and z. If γ ⊆ b c we already have γ ⊆ S c n+1 . Otherwise let π y , π z ∈ γ ∩ ∂b such that γ does not meet b between y and π y , and likewise between z and π z . Because π y , π z ∈ S c n , they cannot be in Sn . Let e = ∂b \ Sn . e is a path-connected circular arc, and is the contribution of ∂b to ∂S n+1 . We have π y , π z ∈ e. Since e is path-connected and contained in S c n+1 , we can complete γ by following e to go from π y to π z , showing that S c n+1 is path-connected. Though Lemmas 7 and 8 are quite remote from the result we want to prove, in essence Lemma 9 implies that whatever medial ball we chose in C(b 0 , +), it cannot contribute to cover S ε in C(b 0 , -). That is why we can process each of these components separately in a greedy way and still achieve a global optimal solution. Formally, we rely on the following corollaries.

Corollary 10 Let b 0 be a medial ball in S. Then we have the three identities:

(C(b 0 , -) ∪ b 0 ) c ∩ S ε = C(b 0 , +) ∩ S ε (C(b 0 , +) ∪ b 0 ) c ∩ S ε = C(b 0 , -) ∩ S ε (C(b 0 , +) ∪ C(b 0 , -)) c ∩ S ε = b 0 ∩ S ε
Corollary 10 simply states that when restricted to S ε , the complement of C(b 0 , +), C(b 0 , -), and b 0 , is the union of the other two subsets.

Proof. We only prove the first equality. We have S ε ⊆ S. Additionally by Lemma 9, S is the disjoint union of C(b 0 , -) ∩ S, b 0 ∩ S, and C(b 0 , +) ∩ S. Hence,

S ε ∩ (C(b 0 , -) ∪ b 0 ) c = S ε ∩ S ∩ (C(b 0 , -) ∪ b 0 ) c = S ε ∩ S ∩ C(b 0 , +) = S ε ∩ C(b 0 , +).
S ε ∩ C(b , -) ⊆ S ε ∩ ( B + ) c = S ε \ B + .
By assumption, b cannot be a candidate to B -, hence by Definitions 2 and 3 (S ε ∩ C(b , -)) \ (b ∪ ( B -)) is non empty. With the previous inclusion, we get the following development. Proposition 12 Algorithm 1 converges to an optimal ε-covering.

S ε ∩ C(b , -) \ Ä b ∪ Ä B - ää = S ε ∩ C(b , -) \ Ä b ∪ Ä B - ä ∪ Ä B + ää = S ε ∩ C(b , -) \ B ⊆ S ε \ B Hence, S ε \ B = ∅ which
Proof. We denote by B algo the ε-covering found by Algorithm 1. We number the balls of B algo by b 1 , . . . , b k , such that for i ≤ j, b i was found before b j . Consider any optimal ε-covering B opt . We assume without loss of generality that B opt only contains medial balls. Indeed, S is a finite union of balls, hence any ball b ∈ B opt is wholly contained in a medial ball. Using consecutive substitutions, we want to build a finite sequence of εcoverings B 0 , . . . , B k that satisfies the properties: The algorithm presented computes in polynomial time an optimal ε ε-covering of any union of balls S such that MA (S) is a forest and MA (S ε ) ⊆ MA(S ε ).

An interesting perspective is to build on this work to design a heuristic algorithm where both conditions on the medial axis are relaxed.

  An additional useful notion is that of T -maximal ball for a collection: given a collection of balls B, b ∈ B is T -maximal in B if for all b ∈ B, either b ≤ T b or b and b are T -unrelated. Likewise, b is T -minimal in B if for all b ∈ B, either b ≥ T b or b and b are T -unrelated. Finally, we extend the notion of degree for any point c ∈ MA (S)

Figure 1 :

 1 Figure 1: T -large and T -small components of a medial ball. x is the root of T . Red segments are points T -smaller than c 0 , blue ones are points T -larger, black ones are T -unrelated.

  Likewise, the domain that still needs to be processed for B should be the intersection, over all b ∈ B, of the domains to be processed for b. Hence the T -large component of B is C(B, +) = ∩ b∈B C(b, +). Owing to Proposition 3, these definitions emphasize the importance of the T -maximal balls of B. Let T -max ( ) be the collection of these T -maximal balls. Then C(B, +) = C(T -max (B) , +) and likewise C(B, -) = C(T -max (B) , -).

Algorithm 1 1 : 3 :

 113 Greedy ε-covering Input: A finite union of balls S Output: An ε-covering B of S Compute a topological ordering of MA (S) 2: B ← ∅ Loop over all pencils in topological order 4:

Figure 2 :

 2 Figure 2: A is the dark shaded area, with B = {b 1 , b 2 } and X = b 0 ∪ b 1 ∪ b 2 . In (a) b 0 is a candidate to B, but in (b) vertex v does not satisfy condition (ii) and A \ X (in red) is non empty.

  Given a ball b = b(c, r) and a point y, there are many ways to test whether y belongs to b or not. By definition, we can compare the distance from y to c, to the radius of b. Here, we rely on the power of y with respect to ball b, which by definition is pow(y, b) = y -c 2 -r 2 . Hence, y belongs to ball b if and only if pow (y, b) ≤ 0. Consider now a pencil of balls [b 1 b 2 ], with b i = b(c i , r i ). For λ ∈ [0, 1], we denote by b λ = b(c λ , r λ ) the ball of pencil [b 1 b 2 ] that is centered at c λ = λc 1 + (1 -λ)c 2 . We argue that then, for any point y, the power of y with respect to b λ is the linear interpolation of its power with respect to b 1 and b 2 . Proposition 4 pow (y, b λ ) = λ pow (y, b 1 ) + (1 -λ) pow (y, b 2 )

6

  Correctness of the algorithm 6.1 Convergence to an ε-covering Lemma 5 Let b 0 and B such that b 0 fulfills both conditions (i) and (ii). Then b 0 is a candidate for B.

Lemma 6

 6 Algorithm 1 converges to an ε-covering in O Ä |MA (S)| 2 ä . Proof. Let n = |MA (S)|. First, we show that Algorithm 1 outputs a collection B algo with size at most 2n, and then that the complexity is at most quadratic. For any partial T -small ε-covering B, let b ∈ T -max (B). There is a unique pencil incident to b that contains balls T -larger than b. Let b 0 > T b be the Tlarge endpoint of that pencil. We show that b 0 is always a candidate to B. Though b 0 may not be a T -maximal candidate, this still implies that there can be at most two medial balls from the same pencil in B algo . Let B 0 = B∪{b 0 }. Because b and b 0 belong to the same pencil, C(B 0 , -) and C(B, -) only differ in the domain of S covered by the pencil [bb 0 ]. This implies the equal-

Lemma 7

 7 Consider a finite union of balls S, and a ball b such that b S. Let S = S ∪ b. Then, S = S ∪ b.

Lemma 9 Figure 3 :

 93 Figure 3: Schematic representation for Lemma 9.

Corollary 11

 11 Consider an ε-covering B. Let B -B be a partial T -small ε-covering, and let b 0 be any Tmaximal candidate to B -. Then B \ B -contains a candidate to B -that is T -smaller than or equal to b 0 . Proof. Let B + = B \ B -. First we prove that B + always contains candidates to B -, and then that one of these candidates is T -smaller than or equal to b 0 . By contradiction, assume that B + is void of candidate to B -. Consider b ∈ B + , T -minimal in B + . By T -minimality of b , for all b ∈ B + , b ⊆ b ∪ C(b , +). Thus B + ⊆ b ∪ C(b , +). By Corollary 10, we deduce that

  is impossible since B is an ε-covering. Thus, B + contains a candidate to B -. Because B -may have several distinct T -maximal candidates, B + may only contain candidates Tunrelated to b 0 . By contradiction assume B + is void of candidate to B -T -smaller than or equal to b 0 . Since B + contains at least one candidate to B -, b 0 cannot be centered at the root of T . By Proposition 3, any ball Tsmaller than or equal to b 0 is a candidate to B -. Hence B + only contains balls that are either strictly T -larger than b 0 , or T -unrelated to b 0 . Therefore, there exists a medial ball b > T b 0 , with b also strictly T -smaller or T -unrelated to balls in B + . By T -maximality of b 0 , b cannot be a candidate to B -. Once again, we have a ball b , T -minimal in B + = B + ∪ {b } which is not a candidate. The same development as above using Corollary 10 yields S ε \ B = ∅, which is still impossible. Therefore, B + must contain a candidate to B -that is T -smaller than or equal to b 0 .

  (a) B 0 = B opt , (b) |B i+1 | = |B i |, ∀i ∈ 0, k -1 , (c) {b 1 , . . . , b i } ⊆ B i , ∀i ∈ 1, k , If such a sequence exists, we immediately deduce that |B algo | = |B opt |, and B algo is also optimal.We proceed by induction. Assume that for 0 ≤ i < k, we have built B 0 , . . . , B i with the above properties.Consider b i+1 . Let B -= {b 1 , . . . , b i }. By construction, B - B i . Let B + = B i \ B -. Algorithm 1 guarantees that B -is a partial T -small ε-covering and that b i+1 is a T -maximal candidate for B -.Hence we can apply Corollary 11 and there is a candidate b to B -, such that b ∈ B + and b ≤ T b i+1 . Then, let B i+1 = (B i ∪ {b i+1 }) \ {b}. B i+1 satisfies both properties (b) and (c), we must prove that it is also an ε-covering. To do so, it suffices to prove that bothC(b i+1 , -) ∩ S ε and C(b i+1 , +) ∩ S ε are contained in B i+1 . Because b i+1 is a candidate to B -, we have C(b i+1 , -) ∩ S ε ⊆ b i+1 ∪ ( B -) ⊆ B i+1 . Also, b ≤ T b i+1 , hence by Proposition 3 we have C(b i+1 , +) ⊆ C(b, +). This implies C(b i+1 , +) ∩ S ε ⊆ C (b, +) ∩ S ε ⊆ ( B i ) \ b ⊆ B i+1 .Thus, B i+1 is an ε-covering, and B algo is an optimal ε-covering.7 DiscussionConsider the following more general covering definition, where S ⊕ε = ∪ y∈S b(y, ε ) is the dilation of S (by ε ):Definition 4 An ε ε-covering of S is a collection of balls B such that S ε ⊆ B ⊆ S ⊕ε .

deg(c0) i=1 C(b 0 , i). Unless c 0 is the