Didier Dubois
email: dubois@irit.fr

On degrees of truth, partial ignorance and contradiction

Keywords: Partial logic, Belnap logic, interval-valued fuzzy sets

In many works dealing with knowledge representation, there is a temptation to extend the truth-set with values expressing ignorance and contradiction. This is the case with partial logic and Belnap bilattice logic. This is also true in interval-valued extensions of fuzzy sets. This paper shows that ignorance and contradiction cannot be viewed as additional truth-values nor processed in a truthfunctional manner.

Introduction

From the inception of many-valued logics, there have been attempts to attach an epistemic flavor to truth degrees. This has led to a very confusing state of facts, and has probably hampered the development of applications of these logics. Indeed, belief is never truth-functional [START_REF] Dubois | Can we enforce full compositionality in uncertainty calculi?[END_REF]. Fuzzy logic is often attacked because it is truth-functional. A well-known example is by Elkan [START_REF] Ch | The paradoxical success of fuzzy logic[END_REF] criticising the usual fuzzy connectives max, min, 1-, as leading to an inconsistent approach. Looking at these critiques more closely, it can be seen that the root of the controversy also lies in a confusion between degrees of truth and degrees of belief. Fuzzy logic is not specifically concerned with belief representation, only with gradual (not black or white) concepts [START_REF] Hájek | The Metamathematics of Fuzzy Logics[END_REF]. However this misunderstanding seems to come a long way. For instance, a truth-value strictly between true and false was named "possible" [START_REF] Lukasiewicz | Philosophical remarks on many-valued systems of propositional logic[END_REF], a word which refers to uncertainty modelling and modalities. Other logics seem to suffer from this kind of confusion such as partial logic closely related to Kleene 3-valued logic, and Belnap's allegedly useful four-valued logic. We claim (see [START_REF] Dubois | On ignorance and contradiction considered as truth-values[END_REF] for details) that we cannot consistently reason under incomplete or conflicting information about propositions by augmenting the set of Boolean truth-values true and false with epistemic notions like "unknown" or "contradictory", modeling them as additional genuine truth-values of their own. Then we consider the case of truth-functional extensions of fuzzy set algebras like interval-valued fuzzy sets and membership/nonmembership pairs of Atanassov.

Truth vs. belief in classical logic

In a previous paper [START_REF] Dubois | Possibility theory, probability theory and multiple-valued logics: A clarification[END_REF] we pointed out that while classical (propositional) logic is always presented as the logic of the true and the false, this description neglects the epistemic aspects of this logic. Namely, if a set B of well-formed Boolean formulae is understood as a set of propositions believed by an intelligent agent (a belief base) then the underlying uncertainty theory is ternary and not binary: it is con-ceivable that some proposition is neither believed nor is disbelieved by a particular agent. Namely It is clear that belief refers to the notion of validity of p in the face of B and is a matter of consequencehood, not truth-values. In fact, one can represent belief by means of subsets of possible truth-values enabled for p by taking propositions in B for granted. Full belief in p corresponds to the singleton {1} (only the truthvalue "true" is possible); full disbelief in p corresponds to the singleton {0} ; the situation of total uncertainty relative to p for the agent corresponds to the set {0, 1}. This set is to be understood disjunctively (both truth-values for p remain possible due to incompleteness, but only one is correct). Under such conventions, the characteristic function of {0, 1} is viewed as a possibility distribution π (Zadeh [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF]). Namely, π(0) = π(1) = 1 means that both 0 and 1 are possible. It contrasts with other uses of subsets of truth-values, interpreted conjunctively, whereby {0, 1} is understood as the simultaneous attachment of "true" and "false" to p (expressing a contradiction, see Dunn [START_REF] Dunn | Intuitive semantics for firstdegree entailment and coupled trees[END_REF]). This is another convention based on necessity degrees They express what can be called epistemic values whereby the agent believes p, believes ¬p, or is ignorant about p respectively.

N (0) = 1-π(1); N (1) = 1-π(0). Then clearly, N (0)
3 Partial Logic vs. Supervaluations

Partial logic starts from the claim that truthvalues of propositions can be left open, and that such undefinedness may stem from a lack of information. This program is clearly in the scope of theories of uncertainty and partial belief, introduced as well to cope with limited knowledge. Other interpretations of partiality exist, that are not considered here. From a historical perspective, the formalism of partial logic is not so old, but has its root in Kleene [START_REF]Kleene Introduction to Metamathematics[END_REF]'s three-valued logic, where the third truth-value expresses the impossibility to decide if a proposition is true or false. The reader is referred to the dissertation of Thijsse [START_REF] Thijsse | Partial Logic and Knowledge Representation[END_REF] and a survey paper by Blamey [START_REF] Blamey | Partial Logic[END_REF].

At the semantic level, the main idea of partial logic is to change interpretations into partial interpretations (also called coherent situations) obtained by assigning a Boolean truth-value to some (but not all) of the propositional variables forming a set P rop = {a, b, c, . . .}. A coherent situation can be represented as any conjunction of literals pertaining to distinct propositional variables. Denote by s a situation, S the set of situations, and V (a, s) the partial function from In partial logic a coherent situation can be encoded as a truth-assignment t s mapping each propositional variable to the set {0, 1 2 , 1}, understood as a partial Boolean truth-assignment in {0, 1}. Let t s (a) = 1 if atom a appears in s, 0 if ¬a appears in s, and t s (a) = 1 2 if a is absent from s. The basic partial logic can thus be described by means of a three-valued logic, where 1 2 (again) means unknown. The connectives can be expressed as follows: 1 -x for the negation, max for disjunction, min for the conjunction, and max(1 -x, y) for the implication. Note that if t s (p) = t s (q) = 1 2 , then also t s (p ∨ q) = t s (p ∧ q) = t s (p → q) = 1 2 in this approach. Besides, this (Kleene-like) three-valued logic is isomorphic to the set of non-empty intervals on {0, 1}, using the ordering 0 < 1, equipped with the interval extension of classical connectives, viewing 1 2 as the interval {0, 1}, the other ones being the singletons {0} and {1}.

P rop × S to {0, 1} such that V (a, s) = 1 if a is true in s, 0 if a is false in s,
Since these definitions express truthfunctionality in a three-valued logic, this logic fails to satisfy all classical tautologies. But this anomaly stems from the same difficulty again, that is, no three-element set can be endowed with Boolean algebra structure! (nor is the set of non-empty intervals on {0, 1}). A coherent situation s can be interpreted as a special set A(s) of standard Boolean interpretations, and can be viewed as a disjunction thereof. A coherent situation can be encoded as a formula whose set of models A(s) can be built just completing s by all possible assignments of 0 or 1 to variables not assigned yet. It represents an epistemic state reflecting a lack of information. If this view is correct, the equivalence s |= T p ∨ q if and only if s |= T p or s |= T q cannot hold under classical model semantics. Indeed s |= T p supposedly means A(s) ⊆ [p] and s |= F p supposedly means A(s) ⊆ [¬p], where [p] is the set of interpretations where p is true. But while A(s) ⊆ [p ∨ q] holds whenever A(s) ⊆ [p] or A(s) ⊆ [q] holds, the converse is invalid! This is the point made by Van Fraassen [START_REF] Van Fraassen | Singular Terms, Truth -value Gaps, and Free Logic[END_REF] who first introduced the notion of supervaluation to account for this situation. A supervaluation SV over a coherent situation s is (in our terminology) a function that assigns, to each proposition in the language and each coherent situation s, the super-truth-value SV (p, s) = 1 (0) to propositions that are true (false) for all Boolean completions of s. It is clear that p is "super-true" (SV (p, s) = 1) if and only if A(s) ⊆ [p], so that supervaluation theory recovers missing classical tautologies by again giving up truth-functionality: p ∨ ¬p is always supertrue, but SV (p∨q, s) cannot be computed from SV (p, s) and SV (q, s). The term "super-true" in the sense of Van Fraassen stands for "certainly true" in the terminology of possibilistic belief management in classical logic. The belief calculus at work in propositional logic covers the semantics of partial logic as a special case. It exactly coincides with the semantics of the supervaluation approach. Assuming compositionality of epistemic annotations by means of Kleene three-valued logic provides only an imprecise approximation of the actual Boolean truth-values of complex formulas [START_REF] Cooman | From possibilistic information to Kleene's strong multi-valued logics[END_REF].

Belnap Four-Valued Logic

Two seminal papers of Belnap [START_REF] Belnap | How a computer should think[END_REF] [START_REF] Belnap | A useful four-valued logic[END_REF] propose an approach to reasoning both with incomplete and with inconsistent information. It relies on a set of truth-values forming a bilattice, further studied by scholars like Ginsberg and Fitting. Belnap logic, considered as a system for reasoning under imperfect information, suffers from the same difficulties as partial logic, and for the same reason. Indeed one may consider this logic as using the three epistemic values already considered in the previous sections (certainly true, certainly false and unknown), along with an additional one that accounts for epistemic conflicts.

The contradiction-tolerant setting

Belnap considers an artificial information processor, fed from a variety of sources, and capable of anwering queries on propositions of interest. In this context, inconsistency threatens, all the more so as the information processor is supposed never to subtract information. So the basic assumption is that the computer receives information about atomic propositions in a cumulative way from outside sources, each asserting for each atomic proposition whether it is true, false, or being silent about it. The notion of epistemic set-up is defined as an assignment, of one of four values denoted T, F, BOTH, NONE, to each atomic proposition a, b, . . .:

1. Assigning T to a means the computer has only been told that a is true. 2. Assigning F to a means the computer has only been told that a is false. The approach relies on two orderings in 4. The information ordering, , such that NONE T BOTH; NONE F BOTH. This ordering reflects the inclusion relation of the sets ∅, {0}, {1}, and {0, 1}, using Dunn convention. It intends to reflect the amount of (possibly conflicting) data provided by the sources. The logical ordering, ≺ , according to which F ≺ BOTH ≺ T and F ≺ NONE ≺ T each reflecting the truth-set of Kleene's logic. It corresponds to the idea of "less true than", even if this may sound misleadingly suggesting a confusion with the idea of graded truth. In fact F ≺ BOTH ≺ T canonically extends the ordering 0 < 1 to intervals on {0, 1}, under Dunn convention and F ≺ NONE ≺ T does the same under possibility degree convention.

Then, connectives of negation, conjunction and disjunction are defined truth-functionally on the bilattice. The set 4 is isomorphic to 2 {0,1} equipped with two lattice structures: The information lattice, a Scott approximation lattice based on union and intersection of sets of truth-values using Dunn convention. For instance, in this lattice the maximum of T and F is BOTH; the logical lattice, based on the interval extension of min, max and 1-from {0, 1} to 2 {0,1} \ {∅} respectively under Dunn Convention (for BOTH ) and possibility degree convention (for NONE). These logical connectives respect the following constraints: (i)They reduce to classical negation, conjunction and disjunction on {T, F}; (ii) They are monotonic w.r.t. ordering ; (iii) p ∧ q = q if and only if p ∨ q = p; (iv)They satisfy commutativity, associativity of ∨, ∧, De Morgan laws.

As a consequence, the restrictions of all connectives to the subsets {T, F, NONE} and {T, F, BOTH} coincide with Kleene's threevalued truth-tables, encoding BOTH and NONE as 1 2 . The conjunction and disjunction operations ∨ and ∧ exactly correspond to the lattice meet and joint for the logical lattice ordering. In fact, BOTH and NONE cannot be distinguished by ≺ and play symmetric roles in the truth-tables. The major new point is the result of combining conjunctively and disjunctively BOTH and NONE. The only possibility left for such combinations is that BOTH∧NONE = F and BOTH∨NONE = T. This looks intuitively surprising but there is no other choice and this is in agreement with the information lattice.

This is not really how a computer should think

Belnap's calculus is an extension of partial logic to the truth-functional handling of inconsistency. In his paper, Belnap does warn the reader on the fact that the four values are not ontological truth-values but epistemic ones. They are qualifications referring to the state of knowledge of the agent (here the computer).

The set-representation of Belnap truth-values after Dunn [START_REF] Dunn | Intuitive semantics for firstdegree entailment and coupled trees[END_REF] rather comforts the idea that these are not truth-values. For instance {1} is a subset of {0, 1} while 1 is an element thereof. Interpreting Belnap's epistemic truth-values as genuine truth-values comes down to confusing elements of a set and singletons included in it.

Belnaps explicitly claims that the systematic use of the truth-tables of 4 "tells us how the computer should answer questions about complex formulas, based on a set-up representing its epistemic state"([2], p. 41). However, since the truth-tables of conjunction and disjunction extend the ones of partial logic so as to include the value BOTH, Belnap's logic inherits all difficulties of partial logic regarding the truth-value NONE. Moreover, equalities BOTH ∧ BOTH = BOTH, BOTH ∨ BOTH = BOTH are hardly acceptable when applied to propositions of the form p and ¬p.

Another issue is how to interpret the results BOTH∧NONE = F and BOTH∨NONE = T. One may rely on bipolar reasoning and argumentation to defend that when p is BOTH and q is NONE, p ∧ q should be BOTH ∧ NONE = F. Suppose there are two sources providing information, say S 1 and S 2 . Assume S 1 says p is true and S 2 says it is false. This is why p is BOTH. Both sources say nothing about q, so q is NONE. So one may consider that S 1 would have nothing to say about p ∧ q, but one may legitimately assert that S 2 would say p ∧ q is false. In other words, p ∧ q is F: one may say that there is one reason to have p ∧ q false, and no reason to have it true. However, suppose two atomic propositions a and b with E(a) = BOTH and

E(b) = NONE. Then E(a ∧ b) = F. But since Belnap negation is such that E(¬a) =
BOTH and E(¬b) = NONE, we also get

E(¬a∧b) = E(a∧¬b) = E(¬a∧¬b) = F. Hence E((a ∧ b) ∨ (¬a ∧ b) ∨ (a ∧ ¬b) ∨ (¬a ∧ ¬b)) = F that is, E( ) =
F which is hardly acceptable again. See Fox [START_REF] Fox | Motivation and Demotivation of a Four-Valued Logic[END_REF] for a related critique.

Interval-valued fuzzy sets

IVFs were introduced by Zadeh [START_REF] Zadeh | The concept of a linguistic variable and its application to approximate reasoning-I[END_REF], along with some other scholars, in the seventies, as a natural truth-functional extension of fuzzy sets. Variants of these mathematical objects exist, under various names (vague sets for instance). The IVF calculus has become popular in the fuzzy engineering community of the USA because of many recent publications by Jerry Mendel and his colleagues. This section points out the fact that if intervals of membership grades are interpreted as partial ignorance about precise degrees, the calculus of IVFs suffers from the same flaw as partial logic, of which it is a many-valued extension.

Definitions

An interval-valued fuzzy set is defined by an interval-valued membership function. Independently, Atanassov [START_REF] Atanassov | Intuitionistic fuzzy sets[END_REF] introduced the idea of defining a fuzzy set by ascribing a membership function and a non-membership function separately, in such a way that an element cannot have degrees of membership and nonmembership that sum up to more than 1. Such a pair was given the misleading name of "Intuitionistic Fuzzy Sets" but corresponds to an intuition that differs from IVFs, although both turned out to be mathematically equivalent notions (e.g. G. Deschrijver, E. Kerre [START_REF] Deschrijver | On the relationship between some extensions of fuzzy set theory[END_REF]).

An IVF is defined by a mapping F from the universe U to the set of closed intervals in [0, 1].

Let

F (u) = [F * (u), F * (u)].
The union, intersection and complementation of IVF's is obtained by canonically extending fuzzy set-theoretic operations to interval-valued operands in the sense of interval arithmetic. As such operations are monotonic, this step is mathematically obvious. For instance, the most elementary fuzzy set operations are extended as follows, for conjunction F ∩ G, disjunction F ∪ G and negation F c , respectively:

[min(F * (u), G * (u)), min(F * (u), G * (u))]; [max(F * (u), G * (u)), max(F * (u), G * (u))]; F c (u) = [1 -F * (u), 1 -F * (u)].
IVFs are a special case of L-fuzzy sets in the sense of Goguen [START_REF] Goguen | L-fuzzy sets[END_REF], so as a mathematical object, it is not of special interest. An IVF is also a special case of type 2 fuzzy set (also introduced by Zadeh [START_REF] Zadeh | Fuzzy Logic and approximate reasoning (In memory of Grigore Moisil)[END_REF]). Of course all connectives of fuzzy set theory were extended to intervalvalued fuzzy sets and their clones. IFVs are being studied as specific abstract algebraic structures [START_REF] Deschrijver | Advances and challenges in interval-valued fuzzy logic[END_REF], and a multiple-valued logic was recently proposed for them, called the triangle logic [START_REF] Van Gasse | Triangle algebras: A formal logic approach to interval-valued residuated lattices[END_REF]. See [START_REF] Walker | The algebra of fuzzy truth values[END_REF] for a careful study of connectives for type 2 fuzzy sets; their results apply to the special case of IVFs.

Paradoxes and their solution

Paradoxes of IVFs are less blatant than those of Kleene and Lukasiewicz three-valued logics (when the third truth-value refers to ideas of incomplete knowledge) because in the latter case, the lack of excluded-middle law on Boolean propositions is a striking anomalous feature. In the case of fuzzy logic, some laws of classical logic are violated anyway. However, the fact that interval-valued fuzzy sets have a weaker structure than the fuzzy set algebra they extend should act as a warning. Indeed, since fuzzy sets equipped with fixed connectives have a given well-defined structure, this structure should be valid whether the membership grades are known or not.

For instance, the fact that min(F (u), F c (u)) ≤ 0.5 should hold whether F (u) is known or not. This is a weak form of the contradiction law. However, applying the truthtables of interval-valued fuzzy sets to the case when F (u) = [0, 1] (total ignorance) leads to min(F (u), 1 -F (u)) = [0, 1], which means a considerable loss of information. The same feature appears with the weak excluded middle law, where again max(F (u), F c (u)) = [0, 1] is found, while max(F (u), F c (u)) ≥ 0.5 should hold in any case. More generally, if the truthvalue t(p) = F (u) is only known to belong to some subinterval [a, b] of the unit interval, the truth-functional calculus yields t(p ∧ ¬p) = min(F (u), 1 -F (u)) ∈ [min(a, 1 -b), min(b, 1a)], sometimes not included in [0, 1 2 ].

In fact, treating fuzzy sets with ill-known membership functions as a truth-functional calculus of IFVs is similar to the paradoxical treatment of partial logic by means of Kleene's threevalued logics, where the third truth value is interpreted as total ignorance. Kleene's three valued logic is more naturally truth-functional when viewed as a simplified variant of fuzzy logic, where the third truth-value means halftrue. The loss of classical tautologies then looks more acceptable. In fact, partial logic is debatably construed as an interval-valued truthfunctional extension of classical This problem cannot be solved by a truthfunctional interval-valued fuzzy logic. A simpler instance of this problem is the one of finding the membership function of a complex combination of IVFs. It comes down to finding the interval containing the truth-value of a manyvalued formula, given intervals containing the truth-values of its atoms. For instance, finding the membership function of F ∩ F c when F is an IVF comes down to solving for each element of the universe of discourse the following problem: maximize (resp. minimize) f (x) = min(x, 1 -x) under the constraint x ∈ In Lukasiewicz logic, using the bounded sum and linear product connectives, inferring in the interval-valued setting comes down to solving linear programming problems [START_REF] Haehnle | Proof Theory of Many-Valued Logic -Linear Optimization -Logic Design: Connections and Interactions[END_REF]. Especially the condition F ∩ F c = ∅ is always trivially valid using linear product, even if F is an IFV, since max(0, x + (1 -x) -1) = 0.

In conclusion, there is a pervasive confusion between truth-values and the epistemic values an agent may use to describe a state of knowledge: the former are compositional by assumption, the latter cannot be consistently so. This paper suggests that such difficulties appear in partial logic, Belnap logic, and interval-valued fuzzy logic. In logical approaches to incompleteness and contradiction, the goal of preserving tautologies of the underlying logic (classical or multivalued) should supersede the goal of maintaining a truth-functional setting. Considering subsets or fuzzy subsets of a truth-set as genuine truth-values leads to new many-valued logics that do not address the issue of uncertain reasoning on the underlying original logic. Such "powerset logics" are special cases of latticevalued logic that need another motivation than reasoning under uncertainty. Our critique encompasses the truth-functional calculus of type 2 fuzzy sets [START_REF] Walker | The algebra of fuzzy truth values[END_REF] as well, since it again considers fuzzy sets of truth-values as truth-values.

In that respect, the meaning of "fuzzy truthvalues" proposed in [START_REF] Zadeh | Fuzzy Logic and approximate reasoning (In memory of Grigore Moisil)[END_REF] is sometimes misunderstood, as they cannot be at the same time genuine truth-values and ill-known ones.

= 1 =

 1 N (1) indicates a strong contradiction. It must be emphasized that {0}, {1}, and {0, 1} are not truth-values of propositions in B.

3 .

 3 Assigning BOTH to a means the computer has been told at least that a is true by one source and false by another. 4. Assigning NONE to a means the computer has been told nothing about a. In view of the previous discussion, the set 4 = {T, F, BOTH, NONE} coincides with the power set of {0, 1}, namely T = {1}, F = {0}, the encoding of the other values depending on the adopted convention: under Dunn Convention, NONE = ∅; BOTH = {0, 1}. It expresses accumulation of information by sources. This convention uses Boolean necessity degrees, i.e. BOTH means N (0) = N (1) = 1, NONE means N (0) = N (1) = 0. With possibility degree convention, NONE = {0, 1}; BOTH = ∅. These subsets represent constraints, i.e., mutually exclusive truth-values, one of which is the right one. NONE means π(0) = π(1) = 1, BOTH means π(0) = π(1) = 0. Then ∅ corresponds to no solution.

  [a, b]. Since the function f is not monotonic, the solution is obviously not (always) the interval [min(a, 1 -b), min(b, 1 -a)] suggested by IVF connectives, it is as follows:f (x) ∈ [a, b] if b ≤ 0.5; it is [min(a, 1 -b), 0.5] if a ≤ 0.5 ≤ b; it is [1 -a, 1 -b] if a ≥ 0.5.Only the first and the third case match the IVF connectives solution.

  |= T ¬p if and only if s |= F p; s |= F ¬p if and only if s |= T p; s |= x p ∧ q if and only if s |= x p and s |= x q, s |= x p ∨ q if and only if s |= x p or s |= x q, for x = T, F .

	and is undefined
	otherwise. Then, two relations are defined for
	the semantics of connectives, namely satisfies
	(|= T ) and falsifies (|= F ):
	s |= T a if and only if V (s, a) = 1; s |= F a if and
	only if V (s, a) = 0;
	s

Proceedings of IPMU'08


Émilie Poisson Caillault

Florentin Vanhelst

Charlet Bastian

Kélig Mahé

Florentin

Otolith age estimation by machine learning approaches

come   L'archive ouverte pluridisciplinaire


Ioannis Z Emiris
email: emiris@di.uoa.gr.

Athanasios Kakargias

Sylvain Pion
email: sylvain.pion@inria.fr.

Monique Teillaud
email: monique.teillaud@inria.fr.

Elias P Tsigaridas

Towards an Open Curved Kernel *

Our work goes towards answering the growing need for the robust and efficient manipulation of curved objects in numerous applications. The kernel of the cgal library provides several functionalities which are, however, mostly restricted to linear objects.

We focus here on the arrangement of conic arcs in the plane. Our first contribution is the design, implementation and testing of a kernel for computing arrangements of circular arcs. A preliminary C++ implementation exists also for arbitrary conic curves. We discuss the representation and predicates of the geometric objects. Our implementation is targeted for inclusion in the cgal library.

Our second contribution concerns exact and efficient algebraic algorithms for the case of conics. They treat all inputs, including degeneracies, and they are implemented as part of the library synaps 2.1. Our tools include Sturm sequences, resultants, Descartes' rule, and isolating points.

Thirdly, our experiments on circular arcs show that our methods compare favorably to existing alternatives using core 1.6x and leda 4.5.

Introduction

Curved objects are becoming increasingly important in computational geometry; one reason, is their wide range of applications, including those in solid modeling, CAD, molecular biology, GIS. Our work is inscribed in a general effort to extend current geometric software from linear to non-linear geometric objects. In particular, this paper describes our work in extending the cgal 1 library with a kernel for curved objects and the related operations. It is clear that such a kernel relies heavily on real algebraic numbers, polynomial equations and systems of polynomials of bounded degree.

Our ultimate goal is to propose a modular and efficient approach to extend the cgal library to manipulate curved objects. The cgal Kernel provides the user mainly with linear objects: points, line segments, triangles. . . and basic operations on them. Circles and spheres are also defined but with very few functionalities. Curves are already present in the so called traits classes of certain specific packages of the cgal Basic library: the arrangement package provides the user with a traits class for conic arcs, the optimization package comes with conics and basic operations on them needed for computing minimum enclosing ellipses, whereas the Apollonius graph package computes the Voronoi diagram of circles.

Our first contribution is the design and implementation of an open kernel for conics and related computations, that we aim at extending towards a more general curved kernel in the future. We show how it may represent the relevant geometric objects and how it can be interfaced with an algebraic module. The design and its implementation have striven for modularity and generality, and are thus parameterized by a geometric linear kernel (ie., for linear objects) and an algebraic kernel. Models (in the C++ Standard Template Library sense [START_REF] Austern | Generic Programming and the STL[END_REF]) for these parameters are provided by cgal and based on synaps2 respectively.

Existing work on arrangements of curves includes work related to the library exacus3 [START_REF] Berberich | A computational basis for conic arcs and boolean operations on conic polygons[END_REF][START_REF] Eigenwillig | Complete, exact, and efficient computations with cubic curves[END_REF][START_REF] Wolpert | Jacobi curves: Computing the exact topology of non-singular algebraic curves[END_REF]] as well as work on the cgal arrangement package [START_REF] Wein | High-level filtering for arrangements of conic arcs[END_REF]. Both of these compute arrangements of arbitrary conics, but only the second software is publicly available. Related work on surface arrangements includes [START_REF] Geismann | Computing a 3-dimensional cell in an arrangement of quadrics: Exactly and actually![END_REF][START_REF] Mourrain | Predicates for the sweeping of an arrangement of quadrics in 3d[END_REF]. Another platform for curves and surfaces, with an emphasis towards geometric modeling, is being prepared [START_REF] Gatellier | Axel: Algebraic software component for geometric modeling[END_REF].

Usually, the main issue is the implementation of the geometric primitives: predicates and constructions. They reduce to manipulations of roots of polynomials or polynomial systems. Existing libraries such as core 4 or leda 5 propose types that support exact comparisons of algebraic numbers of arbitrary degree, provided that they are specified by an explicit expression containing radicals or, more recently, as the root of a univariate polynomial (named the rootOf or diamond operator, respectively). These comparisons rely on lazy refinement of multi-precision approximations and separation bounds [START_REF] Burnikel | A separation bound for real algebraic expressions[END_REF][START_REF] Li | A new constructive root bound for algebraic expressions[END_REF]. The cgal traits class for conic arcs of the arrangement package [START_REF] Wein | High-level filtering for arrangements of conic arcs[END_REF][START_REF] Wein | Cgal based implementation of arrangements of conic arcs[END_REF] depends on such number types. Existing software by the computer algebra community (such as Maple or Axiom) offer generality but lack the efficiency required in our applications.

Alternative methods to achieve exact comparisons of algebraic numbers efficiently, by computing only signs of polynomial expressions in the input data, were studied in [START_REF] Devillers | Algebraic methods and arithmetic filtering for exact predicates on circle arcs[END_REF][START_REF] Karavelas | Root comparison techniques applied to computing the additively weighted Voronoi diagram[END_REF] for second-degree polynomials and in [START_REF] Emiris | Methods to compare real roots of polynomials of small degree[END_REF][START_REF] Emiris | Comparison of fourth-degree algebraic numbers and applications to geometric predicates[END_REF] for degree up to 4. These methods are based on general algebraic tools such as Sturm sequences, resultants and Descartes' rule. Our methods follow this approach and, in addition, use low-degree algebraic numbers for isolating the real roots of polynomials. In the case of conic curves, algebraic numbers are of degree at most 4, and the isolating points are always rational. It is important to note that the same methods should cover a wider class of geometric problems, ranging from Voronoi diagrams of curved objects [START_REF] Karavelas | Root comparison techniques applied to computing the additively weighted Voronoi diagram[END_REF] to computing with kinetic data structures [START_REF] Guibas | A computation framework for handling motion[END_REF]. A recent implementation of exact and general algebraic numbers is proposed in [START_REF] Guibas | A computation framework for handling motion[END_REF].

Our implementations are being made publicly available through cgal and synaps. We support our claims of efficiency by experimental evidence on circular arcs in 5 different configurations. We use the only publicly available implementation of arrangements, which is provided by cgal, to compare our implementation with the cgal traits class for conic arcs that uses leda::real. Our code is never slower and, on most configurations, much faster. We conclude that our methods yield efficient implementations and define a very promising approach for computing arrangements of conics.

The next section discusses the proposed kernel design, and Section 3 outlines the representation of the geometric objects and the geometric primitives. In Section 4 we discuss the required algebraic concepts, namely algebraic numbers and polynomials. This is made concrete in Section 5, where different models for the algebraic kernel are described. Our experimental data is presented in Section 6. We conclude with current and future work.

Curved kernel design

We describe the C++ design chosen for organizing our code, and the kind of interface provided by our kernel. As in [START_REF] Pion | Towards a cgal-like kernel for curves[END_REF], our choices have been heavily inspired by the cgal kernel design [START_REF] Hert | An adaptable and extensible geometry kernel[END_REF] which is extensible and adaptable. Indeed, one of its features is the ability to apply primitives like geometric predicates and constructions either to the geometric objects which are provided by our kernel, or to user-defined objects.

A primary concern is good interoperability with cgal, and thus one of the goals was to be able to reuse the cgal kernel for objects like points, circles and number types. Still, in the philosophy of generic programming, we do not wish to be limited to a particular implementation of these objects, so our curved kernel is parameterized by a BasicKernel parameter and derives from it, in order to include all needed functionality on basic objects, e.g. the number type RT (discussed in Section 4) and the circle type Circle 2.

As will be clear in the sequel, the predicates and constructions make heavy use of algebraic operations. We want to be as independent as possible from a particular implementation of the algebraic operations, so our curved kernel is parameterized by an AlgebraicKernel.

The declaration is the following:

template < typename BasicKernel, typename AlgebraicKernel > class Curved_kernel;

The Curved kernel can be used the following way, for example, in the case when a user wishes to use the cgal Cartesian kernel with the double number type as RT, and his own algebraic kernel, denoted My Algebraic kernel: The interface provided at the geometric level is composed of:

#include <CGAL/
• Types defining the objects. Some of them are inherited from the basic kernel, namely the number type (denoted as RT in the sequel), and basic geometric types such as points, circles, and conics. Some other types are inherited from the algebraic kernel. These types are mainly types for algebraic numbers of degree up to 4 and bivariate polynomials of degree 2.

Finally, some types are defined by the curved kernel itself, mainly: Circular arc 2, Circular arc endpoint 2, Conic arc 2, Conic arc endpoint 2.

• Predicates defined on the above objects; their functionality is available through two interfaces:

The first is based on global (non-member) functions. For example, comparing the abscissae of 2 endpoints can be done as follows: Conic_arc_endpoint_2 p, q; ... if (less_x(p, q)) ... else ...

The second is a functor which is provided by the kernel (through a member function of the kernel). Functors are classes providing a function operator : operator(), which can be called using the calling syntax of normal functions, with the added feature that the functor object can store a state. Functors are mostly useful in generic implementations of algorithms, such as those provided by the STL. They can be used as in the following example, for sorting a list of conic arc endpoints:

CK ck; ... std::list<Conic_arc_endpoint_2> L; ... // Sorts L according to the x-order : L.sort(ck.less_x_2_object()); ...

• Constructions are available through the same double interface as the predicates. For example, the construction that splits an arc at an endpoint (a previously generated intersection) in two arcs is:

Circular_arc_2 c1; Circular_arc_endpoint_2 p; ... std::pair<Circular_arc_2, Circular_arc_2> result; result = split(c1, p);

Geometric objects

We discuss arcs of conic curves in the plane, since this is what we have currently implemented. We have thus provided the tools for cgal to build arrangements, using both the incremental and the vertical sweep line algorithms. Our choices readily extend to higher degree algebraic curves. The representations and predicates below rely on the algebraic concepts of Section 4.

Representation

A conic curve is a curve, provided by the Curved kernel, represented by a bivariate polynomial of total degree 2, whose coefficients are of type RT. The current implementation assumes that this polynomial always contains at least one quadratic term, i.e., x 2 , y 2 or xy. Future work shall extend the implementation in order to include straight lines. On the other hand, curves can be generalized to algebraic (or implicit) curves of higher degree.

Two kinds of points -intersection points and endpoints-are considered in the same way, thus allowing us to have a unique representation. We call endpoint indifferently an endpoint of an arc or an intersection. An endpoint is represented by the two intersecting conics and its coordinates. In the current implementation, these are algebraic numbers of degree at most 4, represented by the RootOf d concept.

This representation is redundant, since the coordinates could be retrieved at any time by a computation on the input curves, but avoiding to recompute them each time they are needed saves time. Moreover, keeping the original curves that define the points allows to perform some kind of elementary geometric filtering of predicates: for instance, to test the equality of two endpoints, we can first compare the curves defining them; computations on the coordinates will be performed only if the defining curves are not the same.

A conic arc is represented by a supporting conic, the two delimiting endpoints and a boolean indicating whether it lies on the upper or lower part of the conic curve. The input of course allows for full curves as well as arbitrary arcs, including non-monotone arcs. These are broken into x-monotone arcs (see make x monotone below) by the cgal arrangements algorithms that fix the choice of axes and orientation.

Main primitives

We now present the main predicates and constructions for conic arcs that are required by the cgal arrangements and that are provided by the curved kernel. In the case of circles, these primitives are simplified.

As will be clear in the description below, each of these geometric operations of the curved kernel calls predicates or constructions on purely algebraic objects, namely the algebraic numbers and the bivariate polynomials of the algebraic kernel. These algebraic primitives are described in Section 4. make x monotone It subdivides the given arc (which may be an entire curve) into x-monotone arcs. It calls x critical points on the equation of the curve, then creates the correct representations of all arcs.

nearest intersection to right Given an endpoint p and two x-monotone arcs, find their first intersection to the right of p. It computes all intersections of the two supporting curves by calling the function solve on the equations of the curves, then applies the operator< on the algebraic numbers representing the x-coordinates of the intersection points and of p. compare y to right Given two x-monotone arcs supported by the conics g 1 , g 2 , and one of their intersection points p = (p x , p y ), such that the arcs are defined to the right of p (i.e. for x larger than p x ), the predicate decides which arc is above immediately to the right of p. If p is not defined as an intersection of g 1 , g 2 , the predicate expresses it as such by calling solve. The goal is to have a rational isolating interval (t, s) for p x . If p is not the rightmost intersection of g 1 , g 2 , the predicate compares the y-roots of g 1 (s, y), g 2 (s, y) by operator<. Otherwise, it calls compare y at x on the right endpoint of an input arc with the smallest abscissa and on the other input arc.

In the case of circles, the predicate is simplified by using the slopes of the tangents at p. compare y at x It decides whether a given arc is above or below a given endpoint γ = (γ x , γ y ), by calling sign at with arguments the polynomial defining the curve supporting the arc, γ x , and γ y . Then, multiply the result by ±1 depending on whether the given arc is on the upper or lower part of its curve. Future optimizations include techniques to use the knowledge of the polynomials defining the curves intersecting at γ.

In the case of a circular arc, the predicate simplifies by using the center.

Algebraic kernel concept

In the C++/STL sense, a concept is a set of requirements that a type must provide in order to be usable by some template function or class. The algebraic kernel appearing as template parameter AlgebraicKernel of the curved kernel Curved kernel (see Section 2) is supposed to provide the latter with algebraic numbers of degree up to 4 and operations on uni-or bi-variate polynomials of degree 2. The two corresponding concepts are detailed in this section and our implementation of them discussed in the next section.

Real algebraic numbers

Most geometric predicates on circular arcs (resp. conic arcs) can be expressed as comparisons involving roots of degree 2 (resp. 4) polynomials. These polynomials are typically univariate resultants whose coefficients are themselves polynomials in the coefficients of the equations of the circles (resp. conics). Since there are several ways to deal with such algebraic numbers, we have tried to factorize as much code as possible between these alternatives. In C++, this means writing code that can act generically (through templates) on different types representing the numbers.

We differentiate here on the various categories of numbers using different C++ types, so that the representation of a number of degree 2, for instance, can be different from that of a number of degree less than 2 (the original curves' coefficients as well as quotients of these numbers), hence we have a set of concepts RootOf d that describe basically the same requirements, for each degree d from 1 to 4. The bridge between the number type storing the curves' coefficients, supposed to be a ring type, named RT in the sequel, and the numbers of degree d is the make root of d function described below.

Approaches.

Dealing with roots of polynomials can be done in several ways that generic code should support:

• approximate handling, using floating point approximation, e.g. C++ double.

• approximate but certified handling using interval arithmetic, for instance CGAL::Interval nt or boost::interval.

For these first two cases, algebraic numbers of degree 2 can be implemented using the sqrt() function and the usual formula to produce an approximation. The corresponding RootOf 2 type is then RT itself. For degrees higher than 2, algebraic numbers could be implemented using the Newton iteration, for instance.

• exact handling, using number types implementing exact comparisons between numbers built in the following ways:

-for degree 2: using the square root function sqrt(), e.g. leda::real or CORE::Expr.

-for degrees > 2: using the so-called diamond operator of leda::real [START_REF] Burnikel | A separation bound for real algebraic expressions[END_REF] whose implementation is in progress, or the CORE::rootOf function of CORE::Expr, which manipulate roots of (currently only square-free) polynomials.

• polynomial representation of these roots using algebraic methods for comparisons [START_REF] Devillers | Algebraic methods and arithmetic filtering for exact predicates on circle arcs[END_REF][START_REF] Emiris | Comparison of fourth-degree algebraic numbers and applications to geometric predicates[END_REF][START_REF] Karavelas | Root comparison techniques applied to computing the additively weighted Voronoi diagram[END_REF]. We provide an implementation of this model, for algebraic numbers of degree up to 4, with the Root of class described in Section 5.1, which has been integrated in the synaps library. We also provide a specialized version, namely Root of 2, restricted to degree 2, described in Section 5.2.

The RootOf d concept.

Given a type RT representing the coefficients of the circles or conics equations, there must be a way to find out the (preferred) type used to store the roots of a degree ≤ 4 polynomial whose coefficients are of type RT. This type must also be the return type of the make root of d function taking RT as the type of the arguments. This type must be defined in the algebraic kernel as T RootOf<d>::type, ie. the AlgebraicKernel must contain: typedef T RootOf<d>::type RootOf d;

The following functions must be defined: • RootOf d make root of d(RT a d , ..., RT a 0 , int i); which returns an object representing the i th real root of the polynomial P (X) = For all the possible models of this concept mentioned above, we have written the necessary functions, and now our kernel can be instantiated with all these number types (see Section 5).

Polynomials

As can be seen from Section 3.2, operations on bivariate polynomials play a crucial role in the evaluation of predicates. For now, the polynomials shall be of total degree 2 and denoted by Pol 2 2, but the concept can be generalized to arbitrary multivariate polynomials. More precisely, the functionalities required are: which computes the pairs of elements of type RootOf d that are the critical points of a polynomial f in the x direction, and copies them in an output iterator in lexicographical order.

• template <class OutputIterator> OutputIterator solve(Pol 2 2 f1, Pol 2 2 f2, OutputIterator res);

which computes the pairs of elements of type RootOf d that are the common roots of two polynomials f 1 and f 2, and copies them in an output iterator in lexicographical order.

• int sign at( Pol 2 2 f, RootOf d γx, RootOf d γy);

which returns the sign of a bivariate polynomial f (x, y) evaluated at algebraic numbers x = γ x and y = γ y .

Models of the Algebraic kernel

Implementations matching the concepts are called models [START_REF] Austern | Generic Programming and the STL[END_REF]. This section discusses models of the concepts related to the algebraic kernel presented above.

The Root of class

Each algebraic number is represented by a polynomial and an index. When an algebraic number is constructed from a polynomial, we compute the discriminant of the polynomial in order to extract the multiple roots, if any, and to decide an isolating interval for this root. By this approach we have several advantages. The polynomial that represents an algebraic number is always square free and, moreover, any multiple root is represented by a lower degree algebraic number, which is rational in all cases except in the case of quartics with 2 double roots. The computation of the isolating intervals is achieved by close formulas using Lemma 1 and is independent of the separating bound of the roots.

Here we discuss polynomials of degree up to 4. Our methods should extend to degree 5 and, eventually, higher degrees. They are based on static, or precomputed, Sturm sequences as in [START_REF] Karavelas | Root comparison techniques applied to computing the additively weighted Voronoi diagram[END_REF][START_REF] Emiris | Methods to compare real roots of polynomials of small degree[END_REF][START_REF] Emiris | Comparison of fourth-degree algebraic numbers and applications to geometric predicates[END_REF]. Our algorithms test the sign of certain quantities, which are polynomials in the coefficients of the input bivariate equations representing the conics. These quantities are compiled in order to reduce execution time.

From a complexity viewpoint, we wish to minimize the degree of the tested quantities in these coefficients and, ultimately, the total number of operations as well. One originality of our approach is based on isolating the real roots by rational numbers, by applying the following fact.

Lemma 1 [START_REF] Sederberg | Isolating the real roots of polynomials using isolator polynomials[END_REF] Given a polynomial P (X) with adjacent real roots γ 1 , γ 2 , and any two other polynomials B(X), C(X), let A(X) := B(X)P (X) + C(X)P (X), where P is the derivative of P . Then A or B have at least one real root in the closed interval [γ 1 , γ 2 ].

Considering the polynomial remainder sequence of P and P , we can obtain, as a corollary, that deg A + deg B ≤ deg P -1. The lemma is applied, as in [START_REF] Emiris | Comparison of fourth-degree algebraic numbers and applications to geometric predicates[END_REF], in order to specify several isolating polynomials, denoted by A or B in the lemma, of degree up to 2, when deg P ≤ 4. The roots of isolating polynomials constitute isolating points, since they isolate the roots of the original polynomial P . In the favorable cases, at least one isolating point is rational for every pair of consecutive real roots.

Even when this is not the case, it is possible to find rational isolating points by considering two or more isolating quadratic algebraic numbers in the interval defined by two roots. In short, for every polynomial of degree up to 4, our implementation provides rational isolating points between any root pair [START_REF] Emiris | Comparison of fourth-degree algebraic numbers and applications to geometric predicates[END_REF].

The maximum algebraic degree of any polynomial in the Sturm sequence is the degree of the resultant of the two polynomials, which is 8 when the inputs are quartics. In order to bound the maximum algebraic degree involved in the comparison of the roots of two quartics we must also consider the evaluation of the Sturm sequences on the endpoints of the isolating intervals of the roots.

Proposition 1 [START_REF] Emiris | Comparison of fourth-degree algebraic numbers and applications to geometric predicates[END_REF] There is an algorithm that compares any two roots of two quartics using Sturm sequences and isolating intervals from lemma 1, and the algebraic degree of the quantities involved is between 8 and 13.

We have implemented static Sturm sequences, including all degenerate cases, i.e. when the degree of one of the input or intermediate polynomials is smaller than its nominal degree. In order to simplify this task we consider an evaluation scheme for the complete Sturm sequence. We can treat all possible evaluations of the Sturm sequence as a binary tree, which has as nodes the evaluation of a term of the sequence and branches according to the sign of the computed quantity. This algorithm is automatically generated.

In conclusion we obtain the Root of class, constructed by a polynomial and an index. It includes the computation of an isolating interval for the algebraic number. Additionally, we have implemented the function sturm(Poly<RT> f, Poly<RT> g, RT a, RT b) which computes the result of the evaluation of the Sturm sequence of f and g, which are of arbitrary degree over an interval [a, b]. We do this computation statically for degree up to to 4 and dynamically (using various well known algorithms) for higher degrees.

Based on the aforementioned tools, Sturm theory [START_REF] Yap | Fundamental Problems of Algorithmic Algebra[END_REF][START_REF] Emiris | Comparison of fourth-degree algebraic numbers and applications to geometric predicates[END_REF] yields the following functionalities. They are in the current release of the synaps library.

• compare(Root of α, Root of β)

Comparison of 2 algebraic numbers of degree ≤ 4.

• sign at(Poly f , Root of α) Determination of the sign of a univariate polynomial of arbitrary degree, evaluated over an algebraic number of degree up to 4.

Implementations of the Root of 2 class

In order to handle circles efficiently, we also provide another concrete model optimized for degree 2 -compared to the more general Root of -which is using the following internal representation:

• three coefficients of type RT specifying the polynomial of degree 2.

• one boolean value specifying whether the smaller of the roots is considered or the other. This class uses specific algebraic methods, based on resultants and Descartes' rule of sign, in order to handle comparisons [START_REF] Devillers | Algebraic methods and arithmetic filtering for exact predicates on circle arcs[END_REF]. Handling degrees higher than 2 is not implemented in this model, so it only handles circles. Our experiments below show that the gain of this specific technique is small. But the main reason for adopting a generic approach in the implementation of root of has to do with programming effort: if we had extended the Root of 2 class and had specialized classes for every degree, we would have to develop a large amount of code, in order to handle all the situations efficiently.

Another idea that we have used to speed up computations substantially when RT is a rational type, such as CGAL::Quotient or multi-precision rational numbers such as those provided by gmp, 6 is to consider the polynomials with coefficients over the ring type defining the numerator and denominator of the rationals, instead of the rationals themselves, by simply multiplying the polynomial equation by all denominators; there are three denominators, since we are dealing with quadratic polynomials. This way, when we manipulate the coefficients of the polynomials, we manipulate multi-precision integers instead of rationals, which prevents the explosion of these numbers and is faster in general.

The Pol 2 2 class

We describe here the implemented methods which offer the functionalities required on bivariate polynomials of total degree up to 2. Although our tests in the next section are limited to the case of circles, we show below that extending them to arbitrary conics is straightforward. Our algorithms have been integrated, as a separate module, in the library synaps 2. 1. In what follows an algebraic number γ is of degree up to 4 and it is represented by a polynomial R γ and an isolating interval

I γ = [a γ , b γ ].
• x critical points(Pol 2 2 f ) Take the derivatives f x , f y with respect to x and y. In order to specify the abscissae (resp. ordinates) of the critical points, we take the resultant of f and f y (resp. f x ) by eliminating y (resp. x). To find the correspondence between x and y coordinates, we consider the slope of the line f y = 0. E.g., if the slope is negative, then the biggest root of R x corresponds to the biggest root of R y . If the slope is zero, then this means that f y = 0 is a horizontal line and R y has one double (hence rational) root.

• solve(Pol 2 2 f 1 , Pol 2 2 f 2 )
We consider the resultants R x , R y of f 1 , f 2 by eliminating y and x respectively, thus obtaining degree-4 polynomials in x and y. The isolating points of the resultants define a grid of boxes, where the intersection points are located. The grid has 1 to 4 rows and 1 to 4 columns; each box contains a simple or multiple root. It remains to decide, for certain boxes, whether they are empty and, if not, whether they contain a simple or multiple root. All multiple roots of the two resultants are either rational or quadratic algebraic numbers. Hence, several cases can be decided by calling sign at with algebraic numbers of degree up to 2.

The rest of the cases reduce to testing if a box is empty, provided it contains at most one intersection point. We can decide the if a box is empty or not by calls to the sign at function. Notice that the number of intersection points in a column (row) can not exceed the multiplicity of the algebraic number. Since the edges of the boxes are computed by the isolating points of the resultants, we can always guarantee that they contain at most one.

Unlike [START_REF] Berberich | A computational basis for conic arcs and boolean operations on conic polygons[END_REF], where the boxes cannot contain any critical points of the intersecting conics, our algorithm does not make any such assumption about the topology of the conics in the boxes, hence there is no need to refine them.

Our approach can be extended in order to compute intersection points of curves of arbitrary degree, provided that we obtain isolating points for the roots of the two resultants, either statically (as above) or dynamically. In generalizing to higher degree, one would compare with existing work, such as [START_REF] Eigenwillig | Complete, exact, and efficient computations with cubic curves[END_REF].

• sign at(Pol 2 2 f , Root of γ x , Root of γ y ) We consider f (X, Y ) as a univariate polynomial with respect to X, and we compute the Sturm-Habicht sequence of R γx and f . In order to find the sign of f evaluated over the algebraic number γ x , we have to evaluate the sequence over the endpoints of the isolating interval of γ x and count the modified sign changes [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]. The polynomials in this sequence are in two variables, in general. To be more precise, they are all in two variables, except the first one which is a univariate polynomial in X and the last one which is a univariate polynomial in Y . When we evaluate the sequence over the endpoints of the isolating interval of γ x , the polynomials become either constant numbers (this is the case of the first polynomial) or univariate polynomials in Y . Therefore, we have to compute the sign of each polynomial in the sequence, evaluated over the algebraic number γ y . This can be done by calling sign at(Poly S i , Root of γ y ), where S i is a polynomial in the sequence, after the evaluation over an endpoint of the isolating interval of γ x . Since the Sturm-Habicht sequences have nice specialization properties, the above procedure works for every specialization of the bivariate quadratic function f . The polynomial with the highest degree is the last one in the sequence, which is of degree 8, with respect to Y .

In order to reduce further the required arithmetic operations, we implemented the computation of the bivariate Sturm-Habicht sequence in MAPLE and we used package codegeneration[optimize], so as to identify common subexpressions. By this technique we reduce the arithmetic operations to 1/3. The entire algorithm for sign at is sketched, in preliminary form, in [START_REF] Emiris | Comparison of fourth-degree algebraic numbers and applications to geometric predicates[END_REF].

6 Experimental results

Traits class for CGAL arrangements

The cgal arrangement package does not use the kernel traits design where predicates and constructions are defined as objects. Instead, it requires that the user gives a traits class with member functions providing the algorithms with those functionalities. Therefore, we wrote a traits class to interface our curved kernel with the arrangement algorithms. This traits class follows the requirements presented in [START_REF] Fogel | Specification of the traits classes for cgal arrangements of curves[END_REF] for both sweep line and incremental7 algorithms.

Benchmarks

The hardware of our experiments was Pentium 4 at 2.5GHz with 1GB of memory, running Linux (2.4.20 kernel). The compiler was g++3.3.2; all configurations were compiled with the -DNDEBUG -O3 flags. The versions of the libraries are: cgal 3.0, core 1.6x, gmp 4.1.2, leda 4.5.

The package used to compute the arrangement is the only publicly available implementation of arrangements, namely the cgal implementation (sweep line version).

The implementation of conic arcs is not finalized, hence not benchmarked. We show tests with 5 different kinds of inputs of circular arcs: Random full circles (RFC). Circles positioned on the cross-points and the centers of the cells of a square grid with cell size 10 4 (G). Configuration G, with every circle perturbed both in radius and center by a random integer in the range [-100,100) (PG). Random monotone arcs (RMA) generated by triplets of random circles (one is the supporting circle and the other two define the endpoints of the arc). The same as RMA, except that arcs may be non-monotone (RNMA). The input size refers to the number of full circles for RFC, G, and PG, and to arcs for RMA and RNMA. All random inputs were generated using random integers of 16 bits.

All experimental data are shown in table 1. The output size per data set is given in terms of endpoints and half-edges, where two half-edges correspond to each arc defined by the arrangement. "CK" indicates the use of our Curved kernel. Lines marked "CGAL" correspond to the conic traits from cgal. Timings in seconds are given in the last 5 columns.

MP Float is a number type from cgal which computes polynomial operations (+, -, ×, <) exactly over floating point values, Quotient is a rational template type from cgal, mpz class and mpq class are gmp types, Lazy is CGAL::Lazy exact nt, a template number type doing lazy evaluation, adapted to wrap our Root of 2 type. Root of 2 is the type described in section 5.2, while Root of2 is a specialized version for degree two of the type described in section 5.1. Dashes indicate that the corresponding test could not be completed mainly due to insufficient memory; this occurs with core and Lazy, the reason being the high precision needed or a large expression tree constructed in conjunction with the large number of coordinates constructed.

We conclude that Root of 2 is most efficient with the mpz class type, however the configuration with mpq class is more general since it can treat rational data. The performance of Root of 2 as compared to Root of2 is the same for all number types tested, hence we do not use all number types with Root of2. Our tuned arithmetic performs better than the more general core (that sometimes aborts due to memory consumption) and leda arithmetic, except for the G configuration, where all intersections are integer points.

Compared to the cgal traits with leda arithmetic, our code is much faster except from the G (grid) configuration, where the two show the same performance. The reason is that the cgal traits use bounding boxes around the conic arcs, and this proves particularly useful in the G configuration. The cgal traits can handle conic arcs in general, while our benchmarks currently handle only circular arcs. Our code for conic arcs is still in preliminary form.

One should note that the G and PG distributions are more easily treated by the algorithm, due to fewer intersections and, in the case of G, due also to lower arithmetic precision required. On the other hand, the random cases yield more intersections, hence a larger computational effort is needed.

Demo

We implemented a demo that was used to produce both pictures below, the first displaying the acronym ECG. The demo uses Qt. 8 It allows to compute an arrangement of elliptic arcs with cgal, either incrementally or with the sweep algorithm. Then it displays the computed arrangement as a set of arcs, together with the endpoints, which are either x-extremal points of each arc, or intersection points between two arcs, or the endpoints of the original arcs.

Future Work

The work described in this paper will be submitted for integration into the cgal Open Source Library. Our curved kernel now contains a solid implementation for arrangements of circular arcs. The polishing of the code for conic arcs is in progress.

The work in [START_REF] Emiris | Methods to compare real roots of polynomials of small degree[END_REF][START_REF] Emiris | Comparison of fourth-degree algebraic numbers and applications to geometric predicates[END_REF] is being extended so as to implement algebraic numbers of arbitrary degree in synaps, which will allow us to deal with implicit curves of arbitrary degree. The algorithms, based on Sturm sequences, have certain similarities with the corresponding class of algorithms implemented in [START_REF] Guibas | A computation framework for handling motion[END_REF]. The latter discusses other approaches, as well. We are currently investigating ways of making our implementations benefit from each other.

Lastly, we are going to study the use of more filtering techniques in the manipulation of algebraic numbers for geometric predicates, which should lead to an improved efficiency.

d

  j=0 a j X j , • bool operator<(RootOf d a, RootOf d b);bool operator<(RootOf d a, RT b); which compare two algebraic numbers, or an algebraic number with a number of the ring type. Similarly, the other comparison operators (>, <=, >=, ==, !=) have to be provided.

Table 1 :

 1 Experimental results /www-sop.inria.fr/prisme/ECG/

	Arcs Traits	NumberType	AlgebraicType	RFC	G	PG RMA RNMA
	150	CK	MP Float	Root of 2<MP Float>	39	1.4	1.8	2.2	7.0
	150	CK	CGAL::Quotient<MP Float>	Root of 2<MP Float>	56	2.0	2.6	3.2	10
	150	CK	::mpz class	Root of 2<::mpz class>	40	1.4	1.7	2.3	7.1
	150	CK	::mpz class	Root of2<::mpz class>	40	1.4	1.7	2.2	7.0
	150	CK	::mpq class	Root of 2<::mpz class>	61	2.0	2.5	3.5	12
	150	CK	CGAL::Lazy<mpz class>	CGAL::Lazy<Root of 2<mpz class>>	73	2.0	2.8	3.5	13
	150	CK	CORE::Expr	CORE::Expr	193	5.8	6.0	5.1	28
	150	CK	LEDA::real	LEDA::real	98.5 2.59 3.96	4.60	20.5
	150 CGAL	LEDA::real	LEDA::real	56.8 1.32 3.15	2.33	13.4
	150			Vertices:	10340	300	572	713	2275
				Half-edges:	40760 1148 1688	1952	7868
	300	CK	MP Float	Root of 2<MP Float>	137	2	5	10	34
	300	CK	CGAL::Quotient<MP Float>	Root of 2<MP Float>	195	3	7	14	51
	300	CK	::mpz class	Root of 2<::mpz class>	137	2	5	10	34
	300	CK	::mpz class	Root of2<::mpz class>	137	2	5	10	34
	300	CK	::mpq class	Root of 2<::mpz class>	216	3	7	15	58
	300	CK	CGAL::Lazy<mpz class>	CGAL::Lazy<Root of 2<mpz class>>	275	3	8	15	64
	300	CK	CORE::Expr	CORE::Expr	-	10	17	20	195
	300	CK	LEDA::real	LEDA::real	374 5.18 11.4	19.0	104
	300 CGAL	LEDA::real	LEDA::real	410 2.62 8.01	10.1	98.3
	300			Vertices:	34890	632 1412	2202	10157
				Half-edges:	138360 2360 4448	7008	38218
	500	CK	MP Float	Root of 2<MP Float>	374	6	7	20	86
	500	CK	CGAL::Quotient<MP Float>	Root of 2<MP Float>	531	8	10	28	128
	500	CK	::mpz class	Root of 2<::mpz class>	372	5	7	20	87
	500	CK	::mpz class	Root of2<::mpz class>	372	5	7	20	87
	500	CK	::mpq class	Root of 2<::mpz class>	587	8	10	31	146
	500	CK	CGAL::Lazy<mpz class>	CGAL::Lazy<Root of 2<mpz class>>	-	8	11	33	167
	500	CK	CORE::Expr	CORE::Expr	-	23	23	57	-
	500	CK	LEDA::real	LEDA::real	1143 10.7 14.9	46.2	257
	500 CGAL	LEDA::real	LEDA::real	2689 5.12 11.8	33.0	395
	500			Vertices:	92664 1000 1952	4967	24819
				Half-edges:	368656 3908 5808 16868	95276

http://www-sop.inria.fr/galaad/logiciels/synaps/

http://www.mpi-sb.mpg.de/projects/EXACUS

http://www.cs.nyu.edu/exact/core/

http://www.algorithmic-solutions.com/enleda.htm

http://www.swox.com/gmp/

All predicates in the traits class are taken from the curved kernel except curves compare y at x to right(c1,c2,p) as used in the incremental setting: the case when p is not a common point of c1 and c2 is not considered in the kernel, and is currently evaluated approximately in the traits (since it has higher algebraic degree, and we believe that using it could be avoided).

http://www.trolltech.com/

Acknowledgments

The authors acknowledge constructive discussions with Lutz Kettner and Bernard Mourrain. They are grateful to Radu Ursu for his help on the graphical interface.

* Work partially supported by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-2000-26473 (ECG -Effective Computational Geometry for Curves and Surfaces), www-sop.inria.fr/prisme/ECG/. Also partially supported by INRIA's project "Calamata", a Team Association between the Galaad group of INRIA and the Department of Informatics & Telecommunications, National University of Athens.

† http://www.di.uoa.gr/˜emiris/index-


Corentin Bon

Ludovic Halby

Paola B Arimondo
email: paola.arimondo@cnrs.fr

Bisubstrate inhibitors: the promise of a selective and potent chemical inhibition of epigenetic "writers"

Keywords: methyltransferases, bisubstrate inhibitors, SAM analogues, substrate analogues, histone, DNA, HMT, DNMT, epigenetics

On January 23, 2020, the Food and Drug Administration approved tazemetostat (TAZVERIK), developed by Epizyme Inc., for patients aged sixteen years and older with metastatic or locally advanced epithelioid sarcoma not eligible for complete resection. It is the first inhibitor of histone methyltransferase (HMT) to be approved. Histone methylation, as other epigenetic mechanisms, is involved in gene expression without changing the underlying DNA sequence. Abnormalities in the epigenetic profile are implicated in various diseases (such as cancer, infectious, autoimmune and neurodegenerative diseases). Transferases are major actors in epigenetic modulations chemically modifying histones and DNA. The Tazemetostat's success story is based on the understanding of the biology of the target protein in certain cancers and a lead optimization process from a high-throughput screening's hit. The biological target is the HMT Enhancer of zeste homolog 2 (EZH2). It is the enzymatic subunit of the Repressive Complex Polycomb 2 (PRC2) that methylates lysine 27 of histone 3 (H3K27), promoting transcription repression. Several cancers are associated with hypermethylation of H3K27, which are due either to a hyperactivity of EZH2 mutants or to a loss of activity of the corresponding demethylases, Ubiquitously-transcribed X chromosome tetratricopeptide repeat protein (UTX). Structure Activity Relationship (SAR) studies of the hit molecule allowed the discovery of EPZ6438, a nanomolar inhibitor of EZH2. EPZ6438 acts as a competitor of the co-factor S-adenosine-L-methionine (SAM) [START_REF]Selective Inhibition of EZH2 by EPZ-6438 Leads to Potent Antitumor Activity in EZH2-Mutant Non-Hodgkin Lymphoma | Molecular Cancer Therapeutics[END_REF], the donor of the methyl group transferred by the enzyme to the lysine, and thus inhibits the methylation of H3K27. The compound showed an extraordinary selectivity against EZH2. As all methyltransferases use SAM as co-factor, it is a challenge to design selective inhibitors that compete with the SAM. Indeed, several other SAM analogues have been synthesised to target HMT, but the selectivity and potency were not sufficient to reach clinical trial [START_REF] Zhang | SAM/SAH Analogs as Versatile Tools for SAM-Dependent Methyltransferases[END_REF].

Importantly, all transferases, such as HMT, DNA methyltransferases (DNMT) and histone acetyltransferases (HAT), bear two pockets: a co-factor binding site and a pocket that binds the substrate to be modified. Chemical strategies are developed to inhibit these enzymes by targeting either the co-factor binding site, the substrate pocket or both at the same time. Single pocket targeting such as the case of Tazemetostat is often not sufficient for selectivity, whereas the targeting of both pockets potentially leads to more potent and selective compounds.

The epigenetic methyltransferases (MTases) HMT and DNMT have over 30 members, which all share the same co-factor to methylate three different substrates (lysine for KMT, arginine for PRMTs and cytosine for DNMT). The discovery of selective inhibitors is highly challenging. The SAM pocket differs among the families of MTases to accommodate the respective substrate and co-factor, orienting the methyl group adaptively to the substrate. Indeed, the orientation of the SAM is different in PRMTs compared to KMTs containing the SET-domain, and even further in DNMTs [START_REF] Campagna-Slater | Structural chemistry of the histone methyltransferases cofactor binding site[END_REF]. Consequently, it is possible to obtain selectivity for one family versus another by imposing a particular bending of the SAM competitor, but further selectivity in the family is made difficult by the high similarity in the binding mode of the SAM [START_REF] Qian | SET domain protein lysine methyltransferases: Structure, specificity and catalysis[END_REF].

However, there are variations of the amino acid sequence of the substrate pocket from one protein to another, and it is thus possible to design small molecules that compete with the substrate and take advantage of the level of methylation, the position in the histone tail or the 3D conformation of the substrate. For example, KMTs methylate in a highly selective way only one specific lysine in the histone tail and can achieve mono-, di-and/or tri-methylation depending on the chromatin state. Both Euchromatic histone-lysine N-methyltransferase 2 (EHMT2), also known as G9A, and suppressor of variegation 3-9 (SUV39) methylate H3K9 but not in the same chromatin state [START_REF] Wu | Structural Biology of Human H3K9 Methyltransferases[END_REF], while the PRMTs achieve either symmetric or asymmetric methylation of arginine. In the case of the DNMTs, potential selectivity could be achieved based on either the small differences in amino acids of the catalytic pocket [START_REF] Erdmann | Targeting DNA Methylation with Small Molecules: What's Next?[END_REF] or some sequence specificity of the DNA sequence around the CpG site [START_REF] Handa | Profound flanking sequence preference of Dnmt3a and Dnmt3b mammalian DNA methyltransferases shape the human epigenome[END_REF], [START_REF] Emperle | The DNMT3A R882H mutant displays altered flanking sequence preferences[END_REF].

The most promising strategy for selective inhibitors resides in targeting both the cofactor and substrate pockets at the same time. This strategy is based on the design of bisubstrate derivatives. Bisubstrate derivatives consists of analogues of the co-factor and analogues of the substrate covalently linked together. A notable case is the transition state analogues (TSA) that consist in the covalent coupling of the substrate and the co-factor exactly. It was the first strategy that led to the discovery of selective inhibitors of kinase proteins [START_REF] Lavogina | Bisubstrate Inhibitors of Protein Kinases: from Principle to Practical Applications[END_REF]. In addition to selectivity, it bears the promise of potency because the free binding energy of the formed conjugate is equal to the sum of the free binding energies of the moieties plus an entropy gain due to the interaction of a single molecule rather than multiple fragments within the protein. Of note, part of the binding energy is generally lost during the conjugation of the components, due to the fact that they lose freedom of orientation in their respective pocket. However, linear decrease in the free bond energy causes an exponential decrease in the dissociation constant and the entropic effect can be up to three order fold increase [START_REF] Lavogina | Bisubstrate Inhibitors of Protein Kinases: from Principle to Practical Applications[END_REF].

Notably, in the design of bisubstrate analogues, the linker that binds the two moieties plays an important role; its nature and length need to be optimised in parallel to the analogues of substrate and co-factor. The linker's optimization depends on the distance between the two pockets and the 3D orientation of the substrate relative to the co-factor. The length dictates how each moiety fits in its respective pocket, while on the nature of the linker will depend its capability to interact or repulse with the interspace-forming amino acids. For example in DNMT1, it has been suggested that a positively charged linker should allow better potency [START_REF] Miletić | In silico design of the first DNA-independent mechanism-based inhibitor of mammalian DNA methyltransferase Dnmt1[END_REF]. Moreover, a preorganization of the moieties using a constrained linker could allow the two parts to be correctly directed toward their respective pockets, optimising the entropy gain. Thus, the linker design is a key point in the modulation for selectivity: it can allow us to optimise the interaction with one enzyme and destabilize the conformation for the others.

There are several examples of success of the bisubstrate strategy targeting the epigenetic MTases. We developed bisubstrate inhibitors of DNMT using aminoquinazoline as an adenosine mimic of the SAM. Various linkers and second substrates were evaluated leading to potent inhibitors of two isoforms of DNMT [START_REF]Rational Design of Bisubstrate-Type Analogues as Inhibitors of DNA Methyltransferases in Cancer Cells[END_REF]. Similarly, a selective PRMT4 inhibitor was discovered using an adenosine derivative coupled to a cytosine derivative as second substrate [START_REF] Halby | Hijacking DNA methyltransferase transition state analogues to produce chemical scaffolds for PRMT inhibitors[END_REF].

Two representative examples of bisubstrates that reached clinical trial are EPZ5676 and JNJ-64619178, targeting DOT1L and PRMT5, respectively. DOT1L is a KMT that is involved in the proliferation of MLL rearranged leukaemia cells [START_REF] Lavogina | Bisubstrate Inhibitors of Protein Kinases: from Principle to Practical Applications[END_REF]. Successive modulations of the three parts of the bisubstrate strategy (co-factor, linker, substrate) resulted in a potent and highly selective DOT1L inhibitor [START_REF] Lavogina | Bisubstrate Inhibitors of Protein Kinases: from Principle to Practical Applications[END_REF]. Epizyme, Inc. minimized the SAM co-factor keeping the recognition pattern of the molecule, while reducing the polarity. Further modifications showed the necessity of a protonated tertiary amine on the linker and the addition of a hydrophobic moiety for activity and selectivity, leading to a first potent bisubstrate inhibitor EPZ4777. By constraining the linker, Epizyme, Inc. obtained the optimised EPZ5676. Most interestingly, the binding mode is most efficient resulting from a change in conformation of the protein upon binding, leading to the occupancy of the SAM pocket and a closure of the substrate pocket by formation of a new hydrophobic pocket adapted to the compound. New bisubstrate-type inhibitors have now been designed by Novartis to obtain more stable, potent and orally available molecules [START_REF] Chen | Discovery of Novel Dot1L Inhibitors through a Structure-Based Fragmentation Approach[END_REF]. PRMT5 (Arginine protein methyltransferase 5) is an enzyme responsible for the symmetric di-methylation of arginine and a therapeutic target in many cancers, as glioblastoma, leukaemia, lymphoma, prostate cancer or colorectal cancer [START_REF] Gerhart | Activation of the p53-MDM4 regulatory axis defines the antitumour response to PRMT5 inhibition through its role in regulating cellular splicing[END_REF]. Two inhibitors have been developed and are in phase I of clinical trials. GSK3326595 occupies only the substrate pocket via a tetrahydro-isoquinoline-type structure making cation-π type interactions and is a reversible inhibitor with a fairly good selectivity [START_REF] Gerhart | Activation of the p53-MDM4 regulatory axis defines the antitumour response to PRMT5 inhibition through its role in regulating cellular splicing[END_REF]. JNJ-64619178 binds simultaneously to the SAM and protein substrate-binding pockets of the PRMT5. It presents high selectivity and a rapid pseudo-irreversible mode-of-action, showing a potent and broad inhibition of cancer cellular growth [START_REF] Brehmer | Abstract DDT02-04: A novel PRMT5 inhibitor with potent in vitro and in vivo activity in preclinical lung cancer models[END_REF]. To date, this molecule is the most potent and selective compound developed against PRMT5, showing the efficiency of this strategy [START_REF] Tao | Discovery of Novel PRMT5 Inhibitors by Virtual Screening and Biological Evaluations[END_REF].

In conclusion, bisusbtrate inhibitors are the most promising for potent and selective inhibition of epigenetic writers. The strategy has the advantage of involving the interaction between two components (the protein and the compound) instead of three (the protein, the substrate and the co-factor). Thanks to this strategy, potent and selective inhibitors were also obtained for acetyltransferases [START_REF] Ngo | Bisubstrate inhibitors to target histone acetyltransferase 1[END_REF], in addition to DNMTs [START_REF]Rational Design of Bisubstrate-Type Analogues as Inhibitors of DNA Methyltransferases in Cancer Cells[END_REF], DOT1L [START_REF] Lavogina | Bisubstrate Inhibitors of Protein Kinases: from Principle to Practical Applications[END_REF] and PRMT5 [START_REF] Brehmer | Abstract DDT02-04: A novel PRMT5 inhibitor with potent in vitro and in vivo activity in preclinical lung cancer models[END_REF]. New bisubstrate analogues are to be explored to target other epigenetic writers. For the design of bisubstrate analogues it is necessary to modulate the three items (co-factor, substrate and linker), which can be challenging. An interesting option is to optimize each moiety through SAR or virtual screening for each pocket and then couple the two fragments by various linkers. Another approach is the in situ chemical coupling of substrate and co-factor analogues, in which the success of the chemical coupling is guided by the target protein [START_REF] Osborne | In situ generation of a bisubstrate analogue for protein arginine methyltransferase 1[END_REF]. In all cases, bisubstrate inhibitors, a classical medicinal chemistry approach, constitute an efficient strategy to obtain selective and potent probes for the writers.

Bibliography:

Commented [l1]: Il faudrait un synonyme pour eviter la repetition