Mélina Verger
email: melina.verger@lip6.fr

Chunyang Fan

Sébastien Lallé

François Bouchet

Vanda Luengo

A Fair Post-Processing Method based on the MADD Metric for Predictive Student Models

Keywords: Algorithmic fairness, Mitigation, Success prediction

Predictive student models are increasingly used in learning environments. However, due to the rising social impact of their usage, it is now all the more important for these models to be both sufficiently accurate and fair in their predictions. To evaluate algorithmic fairness, a new metric has been developed in education, namely the Model Absolute Density Distance (MADD). This metric enables us to measure how different a predictive model behaves regarding two groups of students, in order to quantify its algorithmic unfairness. In this paper, we thus develop a post-processing method based on this metric, that aims at improving the fairness while preserving the accuracy of relevant predictive models' results. We experiment with our approach on the task of predicting student success in an online course, using both simulated and real-world educational data, and obtain successful results. Our source code and data are in open access at https://github.com/melinaverger/MADD.

Introduction

Due to their ability to enhance educational outcomes and support stakeholders in making informed decisions, predictive student models are increasingly used in learning environments [START_REF] Romero | Educational data mining and learning analytics: An updated survey[END_REF]. However, due to the rising social impact of their usage, it is thus now all the more important for these models to not only be sufficiently accurate, but also fair in their predictions. Indeed, the quality of the predictions could influence the adoption of real-world interventions and possibly produce long-term implications for students [START_REF] Holstein | Equity and artificial intelligence in education: Will "AIEd" amplify or alleviate inequities in education?[END_REF].

To evaluate algorithmic fairness, which is broadly defined in [START_REF] Mehrabi | A survey on bias and fairness in machine learning[END_REF], a new metric has been recently developed, namely the Model Absolute Density Distance (MADD) [START_REF] Verger | Is Your Model "MADD"? A Novel Metric to Evaluate Algorithmic Fairness for Predictive Student Models[END_REF]. The interest of this metric is to measure how different a predictive model behaves regarding two groups, independently from its predictive performance, which will be further explained in part 2.1. However, precisely because it is independent from predictive performance, [START_REF] Verger | Is Your Model "MADD"? A Novel Metric to Evaluate Algorithmic Fairness for Predictive Student Models[END_REF] recommend to use it for fairness evaluation on models that already demonstrate satisfying predictive performance to be used in real-world applications. Therefore, we would like to extend the use of this metric to unfairness mitigation as well, that is to say to improve the fairness of accurate but unfair results.

That is why, in this paper, we develop a fair post-processing method based on the MADD metric that improves the fairness of the results outputted by a model without compromising accuracy. It is important to note that this method improves the fairness of the results regarding a single chosen attribute only, since it is based on the MADD metric that evaluates fairness regarding a single attribute as well (see part 2.3). We then experiment with our approach on the task of predicting student success in an online course, using both simulated and real-world educational data, and for which our source code and data are in open access at https://github.com/melinaverger/MADD. Our results show that our method successfully improves the fairness without losing the accuracy of the results.

The remainder of this paper is organized as follows. We first describe the MADD metric in Section 2 in order to explain our MADD post-processing approach in Section 3. Then, we describe how we conducted our experiments in Section 4 and we report our results in Section 5. Finally, we discuss our approach in Section 6, and we conclude our paper in Section 7 with future work. [START_REF] Devroye | Non-Uniform Random Variate Generation[END_REF] The Model Absolute Density Distance (MADD) metric

Motivation of its choice

Among the plethora of fairness metrics that have emerged from recent literature, we chose the MADD for our fair post-processing approach. The first reason is that it is a statistical metric. Indeed, fairness metrics mostly fall into three main classes, counterfactual (or causality-based), similarity-based (or individual), and statistical (or group) criteria [START_REF] Verma | Fairness definitions explained[END_REF][START_REF] Castelnovo | A clarification of the nuances in the fairness metrics landscape[END_REF], but so far the metrics from the first two classes are seldom used in practice [START_REF] Verma | Fairness definitions explained[END_REF]. Using the MADD ensures an easy integration for fairness improvement in existing applications.

The second reason is that, contrary to the other statistical metrics, the MADD is able to capture the severity of the predictive errors between the different groups of students in the data (further explained in part 2.3). Indeed, the principle of the existing metrics consists in making comparisons of any predictive performance of a model across groups (either by independence, separation or sufficiency [START_REF] Kizilcec | Algorithmic Fairness in Education[END_REF]). However, two models producing any similar predictive error proportions across groups can still exhibit very different and possibly harmful errors themselves, which is not captured by these metrics. That is why, since the MADD is precisely not based on predictive performance (then a comparison) but on the intrinsic difference with which a models behaves regarding the groups, this metric is particularly relevant for improving fairness on this distinct aspect.

Preliminaries

To provide a framework for the whole paper, let consider a binary classifier C that aims at predicting student success at a course. C is trained on a dataset {X, Y } n i=1 with n the number of unique students, X the attributes characterizing the students, and Y the binary target variable whose values y i can take 0 for failure and 1 for success. To apply the MADD, C should output both its predictions Ŷ and the predicted probability pi associated to each prediction:

C → { ŷi = {0, 1} , pi ∈ [0, 1]}.
In the rest of the paper, we will focus on the probability related to the success prediction for every student i, i.e. pi ( ŷi = 1), but as it is also equal to 1 -pi ( ŷi = 0), it is simpler to use the notation pi indifferently.

Let also consider one attribute of X, simply noted as a (instead of x (a) conventionally), which will be our attribute of interest, that is to say the attribute regarding which we will evaluate algorithmic fairness. This attribute a should be binary, i.e. composed of two distinct groups of students, G 0 and G 1 . As an example, if a corresponds to having declared a disability, a student could not belong to the group of those who have not (e.g. G 0 ) and the group of those who have (e.g. G 1 ) declared a disability.

Definition

To introduce the metric, the Model Absolute Density Distance (MADD) [START_REF] Verger | Is Your Model "MADD"? A Novel Metric to Evaluate Algorithmic Fairness for Predictive Student Models[END_REF] relies on the comparison between how a model C distributes its probabilities of success predictions pi between the students of a group G 0 and those of a group G 1 from an attribute a. To do so, the calculation of the metric needs two one-dimensional vectors of the same length, noted D a G0 and D a G1 and called density vectors. They both contain the proportions of students of G 0 and G 1 respectively who receive the same predicted probabilities pi (see Figures 1a and1b). These proportions are noted d a G0,k and d a G1,k with k the index of the distinct value of pi . The MADD is thus defined as follows [START_REF] Verger | Is Your Model "MADD"? A Novel Metric to Evaluate Algorithmic Fairness for Predictive Student Models[END_REF]:

MADD D a G0 , D a G1 = m k=0 d a G0,k -d a G1,k ∈ [0, 2] (1)
To better understand what the MADD represents, a visual approximation is given in Figure 1c through the red zone, i.e. the zone where the two continuous density estimates (represented by continuous curves) of discrete D a G0,k and D a G1,k do not intersect. We highlight one advantage of the MADD that is to be bounded, making it objective and comparable for any data-models applications. Indeed, it is bounded between 0 and 2, and the closer the MADD is to 0, the fairer the outcome of the model is (regarding the two groups). More precisely, in the case where the MADD is equal to 0, the model produces the same probability outcomes for both groups so that D a G0 = D a G1 and MADD(D a G0 , D a G0 ) = 0. Conversely, in the most unfair case, where the model produces totally distinct probability outcomes for both groups, the MADD is equal to 2 because we directly sum over the total proportion of both groups, that is to say 1 and 1. This will give some intuition about how to improve fairness based on the MADD in the next section.

3 The MADD Post-Processing Approach

Purpose

As introduced in the previous section, the closer the MADD is to 0, the fairer the outcome of the model is (w.r.t to attribute a), since the distributions of predicted probabilities are no longer distinguishable between the two groups G 0 and G 1 . Thus, to illustrate how a post-processing with the MADD would work, let consider that a model tends to give higher predicted probabilities (i.e. probabilities of success predictions) to a group, e.g. G 0 , than to the other, as shown in Figure 2a. Therefore, the goal of the MADD post-processing is to reduce the gaps between the distributions of both groups, to obtain a result similar to what we can observe in Figure 2b.

Approach

Following up on the previous part, a question can be raised: where should the two distributions coincide? Indeed, should the distribution of G 1 move to the one of G 0 or is there a better location between the two? To solve this issue, let first note as D the distribution related to all students, composed of students from both groups G 0 and G 1 (see the black histogram in Figure 3a). In machine learning, the goal for a model is to approximate the "true" relationship (or prediction function X → Y) between the attributes X in input and the target variable Y in output. As a consequence, we assume that a model that shows satisfying predictive performance outputs a discrete distribution D which should be really close to D, its "true" distribution (see the black line in Figure 3a). Therefore, assuming having such a model, our goal is to make the distributions D a G0 and D a G1 coincide at the place of D, which should best approximate D (see proofs in Appendix A). Indeed, this allows both to reduce the gaps between the two groups hence improve fairness and to prevent a loss in predictive performance. Therefore, the MADD post-processing is based on the following theoretical considerations.

Since D, D a G0 and D a G1 correspond to histograms, then they can be mathematically considered as discrete estimators of the "true" probability density functions (PDFs) they describe (see Figure 3b) [START_REF] Freedman | On the histogram as a density estimator: L2 theory[END_REF], noted as f , f (G0) and f (G1) respectively in the following. We thus want f (G0) and f (G1) to move towards the target f , as the intuition was given in the previous paragraph, but in a linear way because we want to keep the proportionality of their relative distance (see Figure 3c), otherwise it will improve fairness more for one group than for the other. We can now define the new theoretical PDFs f , f (G0) and f (G1) that we will estimate after the post-processing, by introducing a λ parameter, that we call fairness coefficient of distributions convergence, such that:

f (G0) = (1 -λ)f (G0) + λf (2)
f (G1) = (1 -λ)f (G1) + λf (3)
λ can be seen as a distance ratio (see Figure 3c) so that λ ∈ [0, 1], with λ = 0 when the PDFs of G 0 and G 1 are at their initial state and λ = 1 when they both coincide. λ between 0 and 1 means that the distributions are getting closer (see discrete examples of distribution convergence in Figure 5). The challenge is to find the highest λ possible that best improves the fairness without affecting the accuracy of the results. However, in practice, as we do not know the true f , f (G0) and f (G1) , we cannot directly compute f , f (G0) and f (G1) as written in equations 2 and 3 with different values of λ. That is why we introduce fip in the next part.

Implementation

We will generate a mapping function1 , fairness_improved_prediction or in short fip, between the discrete estimates of f , f (G0) , f (G1) (i.e. D, D a G0 , D a G1 ) and the discrete estimates of f , f (G0) , f (G1) that we will note as

D, D a G0 , D a G1 .
The purpose of fip is more precisely to take as inputs the pi available at the output of a trained model and a value of λ, and to output the new fairer predicted probabilities that we note as p

(λ) i (fip: (p i , λ) → p (λ) i ). Consequently, p (λ) i will allow to reconstruct the new D a G0 and D a G1
, as shown in Figure 2b. fip will be generated as follows. Let focus on the group G 0 first. As we want the proportions of students having the same predicted probabilities to be kept even if the predicted probabilities values are changing with the post-processing, we will seek to make the cumulative density function (CDF) of the initial pi of group G 0 being equal to the CDF of the new p (λ) i of group G 0 . Thus, it comes that:

CDF (G0) (p i(G0) ) = CDF (λ) (G0) p (λ) i(G0) (4) =⇒ p (λ) i(G0) = CDF -1(λ) (G0) (CDF (G0) (p i(G0) )) (5)
where

CDF (λ) (G0) = (1 -λ) CDF (G0) +λ CDF, and CDF -1(λ) (G0) is the general inverse function of CDF (λ) (G0
) . We will have the same equations for the group G 1 . In the end, what we do is to compute the different CDFs and CDFs thanks to interp1d and cumtrapz Python functions from scipy library that estimate their "true" equivalents based on the discrete values of pi we have access to, which gives us the core of our fip mapping function. Now we have the ability to compute the p (λ) i , let define an objective function based both on the accuracy and the fairness of the new fairer predicted probability results which depend on λ, to evaluate the outcome of our MADD post-processing method.

Objective Function

Similarly to existing balancing methods between accuracy and penalty values, we define the objective function as follows:

L = (1 -θ) AccuracyLoss(λ) + θ FairnessLoss(λ) (6)
where θ ∈ [0, 1] represents the importance of the accuracy and the fairness in the objective function. Indeed, a larger θ puts more emphasis on fairness, while a smaller θ favors accuracy. The value of θ could be set by an expert depending of what one wants to put more emphasis on, or experimentally determined like what we do with λ in part 5.1 for instance. The AccuracyLoss(λ), compatible with any common loss functions ℓ (e.g. binary cross-entropy loss), and the FairnessLoss(λ) could be defined as follows:

AccuracyLoss(λ) = 1 n n i=1 ℓ p (λ) i , y i (7)
FairnessLoss(λ) = MADD D a G0 , D a G1 (8)
Since the two losses may vary across different scales of values, one should pay particular attention to the choice of ℓ and the way of rescaling both losses to balance them effectively. We will show an example in part 4.2.

Experiments

Process

Our MADD post-processing method, illustrated in Figure 4, can be applied for a fixed θ as follows. Let us have a training, a validation and a test sets. We first train a classifier. Then, we use this trained model on the validation set to output the predictions ŷi,validation and predicted probabilities pi,validation . Next, we apply our fip mapping function with various values of λ to obtain different corresponding p (λ) i,validation . We will thus deduce the new y (λ) i,validation thanks to the classification threshold t. Now, with the new p

(λ) i,validation , y (λ)
i,validation and the true labels y i,validation , we can plot the results of our objective function depending on the λs to find the optimal λ * that will best improve the results of the classifier. Finally, we evaluate the accuracy and the fairness of the results with the chosen λ * on the test set (i.e. with p

(λ * ) i,test ), y (λ * )
i,test and the true labels y i,test ). For the sake of simplification, in the experiments we omit training, validation and test subscripts from the notations but they will be easily deduced from the context.

FairnessLoss exp (λ) = 1 2 MADD D a G0 , D a G1 (10)
For our experiments, we use the objective function L exp composed of the rescaled terms we define as above (Equations 9 2 and 10). Both losses have thus a range of [0, 100%]. Indeed, the AccuracyLoss exp (λ) is the percentage of incorrect predictions, and the FairnessLoss exp (λ) now represents a percentage of dissimilarity between the two distributions. Therefore, the resulting objective function L exp is a weighted average of these two losses based on their importance. However, as a case study, we choose to give in all our experiments the same importance both to the accuracy and the fairness in the post-processing and we fix θ = 0.5. Additionally, it is important to note that in the case of this AccuracyLoss exp (λ), it exactly corresponds to 1 minus the standard accuracy score, which we will exploit in our results in section 5. Our goal will be to experimentally find the optimal parameter λ * that minimizes this objective function L exp , with θ = 0.5.

2 y i corresponds to the new predictions (1 or 0) obtained thanks to the new p (λ) i thresholded with the classification threshold parameter t we primarily set at 0.5 (i.e. y i = 0 when p (λ) i < 0.5, y i = 1 otherwise).

Simulated Data

To demonstrate the validity of our approach, we first experiment our MADD post-processing method on simulated data of pi for which we know the real distributions. Simulated pi(G0) and pi(G1) are thus the predicted probabilities that we would have obtained at the output of a classifier. Let pi(G0) and pi(G1) be represented by some respective PDFs f (G0) and f (G1) . f (G0) and f (G1) are respectively parts of the gamma distribution Γ (4, 1) and the normal distribution N (0.55, 1), properly scaled along the x-axis and normalized within the interval [0, 1]:

f (G0) (x) := 1 C 0 f Γ (4,1) (11x)1 [0,1] (x) C 0 := 1 0 f Γ (4,1) (11x)dx f (G1) (x) := 1 C 1 f N (0.55,1) (10x)1 [0,1] (x) C 1 := 1 0 f N (0.55,1) (10x)dx
Based on the above PDFs, we generate 10, 000 samples of pi(G0) and 10, 000 samples of pi(G1) , whose density vectors D a G0 and D a G1 are displayed in Figure 6a. Moreover, to simulate the true label y i for each student i, we arbitrarily choose to pass the simulated pi value as a parameter of a Bernoulli law: Bernoulli(p i ) ∈ {0, 1}. This will enable us to simulate how a classifier would perform before the post-processing, to compare its results with those obtained after the post-processing. The latter are thus deduced from the classification threshold parameter t that we also arbitrarily set to 0.5 in this paper, and we refer the reader to the footnote 2.

Real-world educational data

As a second testbed for our approach, we use real-world educational data. This data, also used in [START_REF] Verger | Is Your Model "MADD"? A Novel Metric to Evaluate Algorithmic Fairness for Predictive Student Models[END_REF] for fairness evaluation with the MADD, come from the Open University Learning Analytics Dataset (OULAD) [START_REF] Kuzilek | Open University Learning Analytics dataset[END_REF] corresponding to courses offered by The Open University, a distance learning university from the United Kingdom, between 2013 and 2014. The attributes we use to predict whether a student will pass or fail a course are displayed in Table 1. The sum_click attribute was the only one that was not immediately available as is, and we computed it from inner joints and aggregation on the original data. Moreover, we primarily decide in this paper to limit the data to a specific course, tagged "BBB" in [START_REF] Kuzilek | Open University Learning Analytics dataset[END_REF] and composed of 4,740 unique students, because it demonstrates high correlation and high imbalance w.r.t. the gender, which makes it a good candidate to analyze and improve possible algorithmic unfairness regarding this attribute. We learn a logistic classifier on this data, following a 70-15-15% split ratio between the training, validation and test sets.

Results

Simulated Data

We generate 1,000 values of λ with a constant step in its interval [0, 1], and we compute all the corresponding p i (λ), to obtain the relationships between the next three L exp , AccuracyLoss exp (λ), FairnessLoss exp (λ) and λ. In Figure 5, we present how the new predicted probabilities progress with some increasing values of λ. In Figure 6c, we display for all values of λ the evolution of L exp , AccuracyLoss exp (λ) and FairnessLoss exp (λ). We remind that we set θ = 0.5 as we decided to give an equal importance to both the accuracy and the fairness in the post-processing. As we can see (Fig. 6c), on the one hand, when λ increases the accuracy loss increases too (while we want to minimize it), but only slightly (0.361 to 0.390 i.e. about +8%). On the other hand, the fairness loss, which corresponds to half of the MADD, significantly drops as what we look for (0.598 to its lowest at 0.063, i.e. about -90%). In addition, the objective function L exp reaches its minimum value 0.226 at λ * = 0.970, almost 1. Therefore, if we accept to loose about 8% of accuracy (we can make this interpretation because of how we defined our AccuracyLoss exp (λ)), then by choosing λ * = 0.970 we would increase the fairness of the results by 90% w.r.t the MADD criterion. After that, we only have to pass λ * = 0.970 and the pi as inputs of fip to obtain our new fairer predicted probabilities as shown in Figure 6b. We repeate the simulation by generating some other random 10,000 samples for each group, and the results are very similar (see Figure 6d), which strengthens the estimation of λ * being close to 1. To conclude, this experiment, based on a simulated and ideal case study with sufficient data, demonstrates that the MADD post-processing manages to preserve a reasonably similar level of accuracy while significantly improving the fairness of the results. Let us now apply it with real-world data in the next part.

(a) D a G 0 , D a G 1 (i.e. λ = 0) (b) D a G 0 , D a G 1 for λ * (c) First simulation (d) Additional simulation

OULAD Data

Again, we display in Figure 7c the evolution of L exp , AccuracyLoss exp (λ) and FairnessLoss exp (λ), for the values of λ we generated in part 5.1. When λ increases, the accuracy loss remains almost constant (0.332 to 0.336 i.e. about +1%), and the fairness loss significantly drops again (0.431 to its lowest at 0.158, i.e. about -63%). However, the Figure 7c shows a lot more variability than in the previous case study, which comes from the much lower number of samples in the validation set (about 700). This loss in precision makes more challenging to find an optimal λ * . Indeed, we see that the minimum of the objective

Discussion

Both experiments on simulated data and real-world data show that a postprocessing based on the MADD metric successfully improves fairness while preserving a reasonably constant accuracy. The strength of our approach lies precisely on having found, for every possible value of λ, i.e. the fairness coefficient of distributions convergence, how to compute the two new predicted probability distributions to make them fairer and to keep the accuracy preserved. Indeed, the slight change in accuracy can be explained as follows. Since the model predicts success (i.e. 1) for all students whose predicted probabilities exceed the threshold t, then after the post-processing only those whose new predicted probabilities pass the threshold t affect the accuracy (i.e. passing from 0 to 1 in their prediction). More precisely, we found that the accuracy loss is a function of the quantile CDF (λ) (t), and the closer CDF (λ) (t) is to the quantile CDF(t) of the original distribution, the smaller the accuracy loss is, and vice versa. Thus, the selection of the overall distribution as the target for the convergence of the distributions of the two new probabilities makes the change in CDF (λ) (t) small compared to the original distribution, and therefore ensures a small loss of accuracy. Besides, it is important to note the role of t on the students whose prediction changes.

In addition, from the linear relationship the MADD post-processing is based on, it guarantees that the FairnessLoss(λ) will always linearly decrease with λ. Indeed, the FairnessLoss(λ) is twice the MADD of the new predicted probabilities, that are getting linearly closer with λ. Thus, as the MADD linearly decreases while they linearly get closer (because of how the MADD is defined), so do the FairnessLoss(λ).

However, a limitation of our approach is that even if λ = 1, the new generated distributions D a G0 and D a G1 will not overlap exactly, but will be infinitely close as the sample size increases. Indeed, it comes from the fact that the new predicted probabilities are computed via a histogram-based CDF, and the speed of convergence of the histogram as an estimator also depends on the sample size.

Conclusion

In this paper, we present a fair post-processing method based on the MADD metric. We apply this method to the task of predicting student success at the course level, with the code and data in open access at https://github.com/ melinaverger/MADD. This post-processing method allows to improve the fairness of models' results deemed sufficiently accurate but unfair. It does not require to have access to the original data nor the trained model itself. Finally, experimenting with various values of θ is part of our future work, as well as extending our approach to the consideration of multiple attributes for a more global fairness improvement.

A Proofs of 3.2

We set C to be a random variable with probability density function D, representing the predicted probability value of the output of the model C, and S to be a random variable subject to Bernoulli distribution, representing the value of the sensitive parameter a. Thus, D G0 and D G1 are the probability density functions of the conditional distributions C|S = 0 and C|S = 1, respectively. According to the law of total probability, we have: And because for all k ∈ {1, . . . , m}, we have:

P (C ≤ t) = P (C ≤ t | S = 0) P (S = 0) + P (C ≤ t | S = 1) P (S = 1) ⇐⇒ F (t) = F G0 (t) P (S = 0) + F G1 (
d G,k = N G0,k + N G1,k n 0 + n 1 = n 0 d G0,k + n 1 d G1,k n 0 + n 1 = n 0 n 0 + n 1 d G0,k + n 1 n 0 + n 1 d G1,k
Also, f (G0) , f, f (G1) are based on D a G0 , D G , D a G1 , respectively: Therefore, f (G) (x) = n0 n0+n1 f (G0) (x) + n1 n0+n1 f (G1) (x), so f (G0) , f, f (G1) are also collinear (see Figure 3c). This is not a coincidence; in fact, as histogram estimators, when (n 0 , n 1 ) → +∞, f (G0) , f, f (G1) → D a G0 , D G , D a G1 .

B Proof of 3.3

According to Inverse transform sampling [START_REF] Devroye | Non-Uniform Random Variate Generation[END_REF], we have the following two theorems:

Theorem 1. Let A be a distribution and F A be the cumulative distribution function of that distribution. If X obeys the distribution A i.e. X ∼ A, then F A (X) ∼ U [0,1] , where U [0,1] is a uniform distribution over [0, 1].

Theorem 2. Let U ∼ U [0,1] and F -1 A be the generalised inverse function of F A , then F -1 A (U ) ∼ A.

Take G 0 as an example. By definition, the newly generated prediction p

Fig. 1 :

 1 Fig. 1: Representations of the MADD from [9]. (a) Proportions of predicted probabilities for group G 0 . (b) Idem for group G 1 . (c) Visual approximation of the MADD in the red zone, thanks to a smoothing of the histograms (a) and (b) for easier interpretability. The smoothing has been done by kernel density estimation of the histograms [9].

Fig. 2 :

 2 Fig.2: MADD post-processing principle. Example of two distributions of predicted probabilities (as in Fig.1a and 1b), before and after the MADD postprocessing.

Fig. 3 :

 3 Fig. 3: MADD post-processing approach. (a) Illustration of the different distributions. (b) Illustration of a PDF based on an histogram. (c) Linear relationship between the PDFs (continuous space).

Fig. 4 :

 4 Fig. 4: MADD post-processing.

poverty 3 Fig. 5 :

 35 Fig. 5: Effect of the MADD post-processing on the predicted probabilities with increasing values of λ.

Fig. 6 :

 6 Fig. 6: Simulated data results. (a) Histograms of D a G0 and D a G1 from simulated pi(G0) and pi(G1) . (b) Histograms of the new D a G0 and D a G1 . (c, d) Objective function (total loss), accuracy loss and fairness loss.

Fig. 7 :

 7 Fig. 7: Real-world educational data results.

:

  t) P (S = 1) ⇐⇒ D(t) = D G0 (t) P (S = 0) + D G1 (t) P (S = 1) Where F, F G0 , F G1 are the cumulative distribution functions (CDFs) of D, D G0 , D G1 , respectively. Since P (S = 0) + P (S = 1) = 1, f is a linear combination of D G0 and D G1 , and D lies between D G0 and D G1 in the function space (i.e., D G0 , D, D G0 are collinear. This property is also true for estimators obtained from observed values. In fact, the definition of the sequence of the heights of the histogram is: for the m equal sub-intervals k-1 m , k m for all k ∈ {1, . . . , m} on [0, 1], D a G0 := {d G0,k | ∀k ∈ {1, . . . , m}} , with d G0,k := N = {d G1,k | ∀k ∈ {1, . . . , m}} , with d G1,k := N {d G,k | ∀k ∈ {1, . . . , m}} , with d G,k := N G0,k + N G1,k n 0 + n 1 := 1 n 0 + n 1 i∈G 1 pi∈Ik

f

  (G0) (x) := m k=i d G0,k 1 x∈I k f (G1) (x) := m k=i d G1,k 1 x∈I k f (x) := m k=i d G,k 1 x∈I k

  (CDF (G0) (p i )), and by Theorem 1, we haveCDF (G0) (p i ) ∼ U [0,1] , so CDF -1(λ) (G0) (CDF (G0) (p i ))obeys the newly generated distribution according to Theorem 2. Furthermore, since the CDF is monotone increasing and the inverse function does not change the monotonicity, CDF -1(λ) (G0) is also monotone increasing, which means that ∀i, j, pi ≥ pj =⇒ p conclusion on G 1 follows in the same way.

Table 1 :

 1 Attributes used from the OULAD[START_REF] Kuzilek | Open University Learning Analytics dataset[END_REF].

	Name	Attribute type Description
	gender	binary	the students' gender
	age	ordinal	the interval of the students' age
	disability	binary	indicates whether the students have declared a disability
	highest_education	ordinal	the highest student education level on entry to the course

Here, not a mathematical function, but a programming function. See details at https://github.com/melinaverger/MADD.

Named as imd_band in the original data.


Christina Katsamaki

Fabrice Rouillier

Elias Tsigaridas

Exact Convex Hull Computation for Plane and Space Parametric Curves

Keywords: Convex hull, parametric curve, bit-complexity, polynomial system

We consider the problem of the computing the boundary of the convex hull of rational parametric curves in R 2 and in R 3 . The boundary of the convex hull is a semi-algebraic set and an exact representation of it breaks it down to a combination of line segments and arcs of the curve for the 2D case, and of triangles and surface patches for the 3D case. For both plane and space curves, we provide an algorithmic solution together with bit-complexity estimates. We show that the computation of the convex hull's boundary reduces in both cases to univariate and bivariate solving and to isolating roots of a univariate polynomial with coefficients in a multiple field extension. We express the bit-complexity with respect to the bit-complexity of the latter operation. Leveraging the results of Katsamaki and Rouillier [ISSAC '23], offers asymptotic upper bounds on the total bit-complexity.

Introduction

For any subset of R n , where n ≥ 1, its convex hull is defined as the smallest convex set that contains it, or in more technical terms, as the intersection of its supporting halfspaces [START_REF] Brøndsted | An Introduction to Convex Polytopes[END_REF]Thm. 4.5]. Convex hull computations are fundamental in computational geometry with direct applications in motion planning [START_REF] Zhou | Bézier curve based smooth path planning for mobile robot[END_REF][START_REF] Yang | A path planning algorithm based on convex hull for autonomous service robot[END_REF], computer vision [START_REF] Rui | Curves and surfaces in computer vision[END_REF] and geometric modeling systems [START_REF] Elkadi | Algebraic Geometry and Geometric Modeling[END_REF][START_REF] González-Vega | Algebraic methods in computer aided geometric design: Theoretical and practical applications[END_REF]. Notably, convex hulls of non-linear objects arise naturally in optimization [START_REF] Jean B Lasserre | Convexity in semialgebraic geometry and polynomial optimization[END_REF][START_REF] Blekherman | Semidefinite Optimization and Convex Algebraic Geometry[END_REF] and learning theory [START_REF] Cucker | On the mathematical foundations of learning[END_REF][START_REF] Sra | Optimization for Machine Learning[END_REF]. We focus on non-linear convex hulls, and in particular of parametric curves in R 2 and in R 3 . Let C be an algebraic curve over R n , parametrized by ϕ : R R n t → ϕ 1 (t), . . . , ϕ n (t) = p 1 (t) q 1 (t) , . . . , p n (t) q n (t) ,

where p i , q i ∈ Z[t] have degree at most d and bitsize τ and gcd(p i (t), q i (t)) = 1, i ∈ [n]. For I ⊆ R, we denote by conv(ϕ(I)) the convex hull of ϕ(I). For the rest of this paper, ϕ(I) is a compact subset of R n . When n = 2, the boundary of conv(ϕ(I)) consists of a combination of Email addresses: christina.katsamaki@inria.fr (Christina Katsamaki), Fabrice.Rouillier@inria.fr (Fabrice Rouillier), elias.tsigaridas@inria.fr (Elias Tsigaridas) smooth curved arcs and segments joining two points on the curve (Fig. 1(a)). When n = 3, it is a combination of triangles and ruled (developable) surface patches (Fig. 1(b)). We design algorithms for the boundary description in these cases and we study their bit-complexity.

Parametric curves stimulated our interest since the parametric representation has already been proven advantageous in the topology computation; for parametric curves in R n the bit-complexity is linear in n, whereas for the implicit case the dependence in n seems to be exponential. In particular, for plane curves the bit-complexity of the implicit and parametric case coincides [START_REF] Katsamaki | On the geometry and the topology of parametric curves[END_REF] but for space curves the bit-complexity gap is already of order O(d 2 ), where d is the degree of the polynomials involved [START_REF] Cheng | An Improved Complexity Bound for Computing the Topology of a Real Algebraic Space Curve[END_REF]. Parametric curves come up in various applications in control theory [START_REF] Kurbatskiȋ | Convex hulls of a curve in control theory[END_REF], in machine learning [START_REF] Staerman | The area of the convex hull of sampled curves: a robust functional statistical depth measure[END_REF] or in chemical engineering [START_REF] Ciripoi | Computing convex hulls of trajectories[END_REF].

Previous work. There is a series of combinatorial algorithms for computing the convex hull of plane curved arcs in parametric form [START_REF] Schaffer | Convex hulls of piecewise-smooth jordan curves[END_REF][START_REF] Dobkin | Computational geometry in a curved world[END_REF][START_REF] Bajaj | Convex hulls of objects bounded by algebraic curves[END_REF][START_REF] Jia | On the convex hulls of parametric plane curves[END_REF]. However, in all these approaches, there are assumptions on the monotonicity and/or the total curvature of the arcs and they rely on several oracles whose running time can be expensive, e.g., oracles for the computation of bitangents, that are lines tangent to the curve at two points. Bitangents' computation is a problem of independent interest; among other works (e.g. [START_REF] Lee | Primitive geometric operations on planar algebraic curves with gaussian approximation[END_REF][START_REF] Parida | Common tangents to planar parametric curves: a geometric solution[END_REF]), of particular interest is the one of Johnstone [START_REF] Johnstone | A parametric solution to common tangents[END_REF], that reduces the problem of finding common tangents between a pair of parametric curves to the intersection of parametric curves in a dual space. Then, he applies his method on the convex hull computation of a smooth paramatric plane curve [START_REF] Johnstone | Giftwrapping a curve with the convex hull[END_REF]; the bitangents now correspond to multiple points of the dual curve. After computing the bitangents, he constructs the convex hull by walking along the curve, starting from a point on the convex hull and leaping, every time a bitangent is found, to the other end of the segment. Essentially, with this method we walk along the curve by walking along the parameter interval. However, it applies only to smooth curves. A more general approach for plane parametric curves with possible self-intersections is proposed by Elber et al. [START_REF] Elber | The convex hull of rational plane curves[END_REF]. They find the parameter intervals that correspond to the arcs of the curve on the boundary, by means of a projection of a plane curve. Then, they sort the arcs with respect to their normal angles and connect them accordingly with segments whenever there is a gap. So, here, the sorting compensates for the fact that now the curve has self-intersections and the connections of the arcs of the curve are not trivial. In practice, computing the arcs of the curve that are on the boundary of the convex hull and sorting them is not straightforward. For an exact algorithm and an analysis of its bit-complexity, a precise algebraic formulation of the problem is needed. Moreover, the presence of cusps is not considered.

For space curves, Sedykh provides a detailed study of the singularities of the convex hull's boundary [START_REF] Sedykh | Structure of the convex hull of a space curve[END_REF]. Nevertheless, in our case, a complete classification is not necessary. Seong et al. [START_REF] Seong | The convex hull of freeform surfaces[END_REF] present an algorithm for the computation of the convex hull, that is extension of the work of [START_REF] Elber | The convex hull of rational plane curves[END_REF] for plane curves. They describe the boundary of the convex hull as a combination of developable surface patches and plane patches (triangles). The plane patches are found by solving systems of polynomial equations and the developable surface patches by tracing an implicit plane curve that expresses a bitangent condition. As with the algorithm for plane curves, cusps are not treated and there are no bit-complexity estimates. There is a series of important works that nevertheless do not give any information on the facial structure of the boundary; this includes the computation of the algebraic boundary [START_REF] Ranestad | The convex hull of a space curve[END_REF][START_REF] Ranestad | The convex hull of a variety. Notions of Positivity and the Geometry of Polynomials[END_REF] or the representation as the projection of a spectrahedron [START_REF] Henrion | Semidefinite representation of convex hulls of rational varieties[END_REF][START_REF] Leslie | Real algebraic geometry in convex optimization[END_REF].

Contribution. We propose an algorithm for the convex hull computation of plane parametric curves, as well as one for parametric curves in R 3 . The algorithms apply to any curve, as long as it is properly reparametrized (see [START_REF] Pérez-Díaz | On the problem of proper reparametrization for rational curves and surfaces[END_REF] for an algorithm and [START_REF] Katsamaki | On the geometry and the topology of parametric curves[END_REF] for an analysis of its complexity) and require in the input a parameter interval I ⊂ R, such that ϕ(I) is compact (Rem. 1). The algorithms share the basic idea and they both rely on our Support predicate (Sec. 3) that applies to any dimension and checks if a given hyperplane is a supporting hyperplane for the curve (see Sec. 2 for a definition). The latter problem is reduced to a condition of sign-invariance of a univariate polynomial. We remark that for implicit curves designing such a predicate is not straightforward.

The boundary of the convex hull of plane parametric curves comprises of arcs of the curve and line segments, whose types we classify in Def. 2. The first step of the algorithm is to compute all these line segments, by solving some polynomial systems. However, among the solutions we obtain segments that do not lie on a supporting line to the curve and thus, they are not on the boundary of conv(ϕ(I)) (see Fig. 2 for an example). The second step consists of decomposing the curve at the endpoints of these segments; in this way, every arc of the decomposition is either entirely on the boundary of the convex hull, or it is contained in its interior. This is equivalent to decomposing the parameter interval I at the parameters that correspond to the segments' endpoints. At the third step, we start from a point on ϕ(I), we follow the branches of the curve one by one and we check for every branch if it is on the boundary of the convex hull by calling the Support predicate for an arbitrary tangent line at the interior of the branch. The last step, amounts to connecting the branches that are on the boundary accordingly with line segments. If the endpoint of a branch is smooth, then determining the segment is trivial, since it lies on the tangent line (and the other endpoint has been found at the first step). When the endpoint is not smooth (i.e., cusp or endpoint of ϕ(I)), we check all the possible segments by employing the Support predicate of Sec. 3.

The boundary of the convex hull of curves in R 3 consists of a combination of triangle facets, whose types we classify in Def. 8, and of some surface patches (Def. 9). The surface patches are ruled (they are generated by line segments connecting two points on the curve) and also developable. They are part of the bisecant surface (Eq. ( 8)), which is traced through the bisecant curve (Eq. ( 7)), an implicit plane curve in the space of parameters. Finding the surface patches on the boundary is equivalent to determining certain branches of the bisecant curve. The algorithm follows the same line as in the 2D case. First, we compute the triples of parameters that correspond to triangle facets, through solving some polynomial systems. At the second step, we split the graph of the bisecant curve into branches by computing a special purpose Cylindrical Algebraic Decomposition (CAD) of I. The third step is to identify the surface patches that are on the boundary of the convex hull. They correspond to branches of the bisecant curve. The Support predicate is used again to find the branches of the bisecant curve that correspond to surface patches. At the last step, we connect the surface patches with triangle facets. Triangles with a smooth vertex that are on the boundary are revealed by the endpoints of the branches of the bisecant curve. We call the predicate Support for the planes on which there are triangles that do not have any smooth vertex. Then, the triangles that do not belong on a supporting plane are discarded.

Our algorithms are built upon the algorithms of [START_REF] Elber | The convex hull of rational plane curves[END_REF] for plane curves and of [START_REF] Seong | The convex hull of freeform surfaces[END_REF] for 3D curves. These approaches present challenges when it comes to implementation and lack analysis of their computational complexity. So, our goal is to bridge the gap between a theoretical approach and one that can be practically implemented in a working system. Moreover, linear facets (segments or triangles) with non-smooth vertices (cusps or endpoints of ϕ(I)) require special treatment. This is done at the last step of our algorithm, where we check if the corresponding lines or planes are supporting for ϕ(I). We also prove that this operation dominates the bit-complexity. When the facets have a smooth vertex, it is not necessary, since the tangency condition at the smooth point defines the facet uniquely.

A bit-complexity analysis, up to our knowledge, has been missing from literature. Our main challenge was to minimize the bit-complexity by identifying the appropriate algebraic formulation that could eliminate expensive operations. By exploiting the problem's geometry, we show that treating the linear facets with non-smooth vertices at the last step amounts to isolating the roots of a zero-dimensional system of the form

{F 1 (X 1 ) = • • • = F N (X N ) = F(X, Y)}.
We denote the bit-complexity of this operation by C(M, Λ, N) (Def. 3). We emphasize that the last polynomial might not be square-free, if we consider it as univariate polynomial in Y. Since there has not been extensive work on the complexity of isolating roots of systems of this form, we express the bit-complexity with respect to d, τ and C(M, Λ, N). We employ algorithms for univariate and bivariate solving, and the resulting bit-complexities are in O B d 7 + d 6 τ + C (d, τ, 2) for 2D curves (Thm. 4), and in O B (d 10 + d 9 τ) + C(d, d 6 τ, 1) + C(d, d + τ, 3) for 3D curves (Thm. 11). Using [START_REF] Daouda | Bounds for polynomials on algebraic numbers and application to curve topology[END_REF]Prop.19] for the case where N = 1 and the results of [START_REF] Katsamaki | On isolating roots in a multiple field extension[END_REF], the previous bit-complexities become O B d 10 + d 9 τ for plane curves and O B d 13 + d 12 τ for space curves. Alternatively, one can employ the Las-Vegas algorithm of [START_REF] Brand | On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection[END_REF] for N × N zero-dimensional polynomial systems. Then, by denoting by ω ≈ 2.372873 the exponent in the complexity of matrix multiplication, the bit-complexities become O B (d 2ω+5 (d + τ)) ≈ O B (d 9.75 (d + τ)) for plane curves and O B (d 3ω+7 (d + τ)) ≈ O B (d 14.12 (d + τ)) for 3D curves. So, our results lead to lower bitcomplexity estimates. A preliminary version of our algorithms is implemented in Maple (examples in Sec. 6).

Background on rational curves

For the sake of generality, we introduce some basic notions for rational curves in R n and their convex hull. Let C be an algebraic curve over R n , parametrized by ϕ in Eq. [START_REF] Bajaj | Convex hulls of objects bounded by algebraic curves[END_REF]. Then, C is the Zariski closure of ϕ(R). We call ϕ(t) a parametrization of C. We say that the parametrization is of size (d, τ) when the polynomials p i , q i have degree at most d and bitsize τ, i ∈ t 2 +1 , -8t(t 2 -1)(t 4 -6t 2 +1) t 8 +4t 6 +6t 4 +4t 2 +1 , (b) segments tangent to the curve at two points or more (in blue), (c) the ones that are on the convex hull (in red).

proper, reparametrization algorithms exist, e.g., [START_REF] Pérez-Díaz | On the problem of proper reparametrization for rational curves and surfaces[END_REF] (see [START_REF] Katsamaki | On the geometry and the topology of parametric curves[END_REF] for an analysis of its complexity). Without loss of generality, we assume that no component of the parametrization ϕ is constant. The point at infinity, p ∞ , is the point on C we obtain for t → ±∞ (if it exists). The tangent vector of the curve at a point p = ϕ(t) is ϕ ′ (t).

Singular points on the curve correspond to shape features that are known as cusps and selfintersections of smooth branches. Self-intersections are multiple points, i.e., points on C with more than one preimages. The parameters that correspond to pairs of multiple points are obtained by solving the square polynomial system [START_REF] Katsamaki | On the geometry and the topology of parametric curves[END_REF]Lem. 11]:

h i (s, t) := p i (s)q i (t) -q i (s)p i (t) s -t , for i ∈ [n]. (2)
Cusps are points on the curve where the tangent vector is the zero vector. This is a necessary and sufficient condition when the parametrization is proper [START_REF] Manocha | Detecting cusps and inflection points in curves[END_REF]. It holds that h i (t, t) = ϕ ′ i (t)q 2 i (t), for i ∈ [n]. Therefore, a parameter that gives a cusp of C is a root of

H(t) := n i=1 h 2 i (t, t) (3)
(see [START_REF] Katsamaki | On the geometry and the topology of parametric curves[END_REF]Lem. 4.1]). Poles are parameters for whom ϕ is not well-defined, i.e., t ∈ R such that i∈[n] q i (t) = 0. We adopt the definitions of [START_REF] Brøndsted | An Introduction to Convex Polytopes[END_REF] of a supporting halfspace and supporting hyperplane for sets in R n . Let C be a non-empty set in R n . A supporting halfspace of C is a closed halfspace K in R n such that C ⊂ K and H ∩ C ∅, where H denotes the bounding hyperplane of K. A supporting hyperplane of C is a hyperplane H in R n which bounds a supporting halfspace. If C is not contained in H, then H is a proper supporting hyperplane. Then, the convex hull of a set in R n , is the intersection of its supporting halfspaces.

Remark 1. Let I ⊂ R. For the convex hull conv(ϕ(I)) to be a compact subset of R n , I has to be either a union of closed intervals not containing any poles of ϕ or a union of such closed intervals and intervals of the form

(-∞, a], [a ′ , +∞), for a ≤ a ′ , a, a ′ ∈ R, if p ∞ exists.

Support: a predicate for parametric curves in R n

Given the implicit equation of a hyperplane ⟨a, x⟩ + c = 0, where a, x ∈ R n and c ∈ R, the Support predicate decides if it is a supporting hyperplane of ϕ(I). By definition, this holds if the hyperplane bounds a supporting halfspace of ϕ(I). Then, the convex hull of the intersection points of ϕ(I) and the hyperplane is a face on the boundary of the convex hull of ϕ(I) (see Fig. 3 for an example in two dimensions). Given the parametric representation of the curve, we can reduce the support test for the hyperplane in question to a condition of sign-invariance; for the hyperplane defined by ⟨a, x⟩ + c = 0 is supporting for ϕ(I) if and only if ⟨a, ϕ(t)⟩ + c ∈ R(t) has at least one root in I and is sign-invariant in I. So, we just have to isolate the real roots of ⟨a, ϕ(t)⟩ + c, since this allows to determine its sign over I.

Convex hull of parametric curves in R 2

Let ϕ(t) = (ϕ 1 (t), ϕ 2 (t)) = p 1 (t) q 1 (t) , p 2 (t) q 2 (t) (defined as in Eq. ( 1)) be a proper parametrization of a plane curve C and I ⊆ R, s.t. ϕ(I) is compact (see Rem. 1).

Assumptions.

(i) The point at infinity, if it exists and it is in ϕ(I), is not endpoint of any segment. Otherwise, we will not be able to obtain these segments as solutions of a polynomial system. We can reparametrize the curve to ensure that the point at infinity is not a segment's endpoint (Las Vegas algorithm in expected time O B (d 2 + dτ) [START_REF] Katsamaki | On the geometry and the topology of parametric curves[END_REF]Lem.7]). (ii) The real subset I has k ∈ O(1) boundary points of constant bitsize.

The facets of conv(ϕ(I)) are line segments joining two (or more) points on the curve. The boundary also consists of one-dimensional families of points of C, which are zero-dimensional faces; they assemble to smooth arcs of the curve (Fig. 1(b)). We will consider these arcs also as facets, by abuse of terminology. In the next definition, we classify the line segments on the boundary in several types (see also Fig. 4). For the set I ⊂ R, we denote by bd(I) its boundary.

Definition 2 (Types of line segments). We distinguish the following types of line segments (I-VI) on the boundary of conv(ϕ(I)) according to their endpoints: I. bitangent segments: on the common tangent line of two or more smooth points of ϕ(I), II. cusp-curve segments: connecting a cusp and a smooth point on the curve, lying on the latter point's tangent line, III. cusp-cusp segments: whose endpoints are both cusps, IV. endpoint-curve segments: connecting a point given by a parameter in bd(I) and a smooth point on the curve, lying on the latter point's tangent line, V. endpoint-cusp segments: connecting a point given by a parameter in bd(I) and a cusp, VI. endpoint-endpoint segments: segments connecting two points given by parameters in bd(I).

Algorithm

Step 1: Computing the segments. We compute all segments of types I to VI for ϕ(I) (Def. 2). They form a superset of the set of segments that are on the boundary of conv(ϕ(I)) (Fig. 2). Each segment has a type (I to VI) and it is determined by two parameter values, say a and b, such that ϕ(a) and ϕ(b) are the segment's endpoints respectively. We find the parameters that correspond to each type of segments by solving a polynomial system and we denote by S the set of all these pairs of parameters. We assume that for a given pair of parameters in S we can determine the type of the corresponding segment in constant time.

We consider the equations in Z(s, t)

⟨ϕ(s) -ϕ(t), (-ϕ ′ 2 (s), ϕ ′ 1 (s))⟩ = 0 , ⟨ϕ(s) -ϕ(t), (-ϕ ′ 2 (t), ϕ ′ 1 (t))⟩ = 0 . (4)
We can easily verify that the pairs of parameters corresponding to segments of Types I to III satisfy these equations. We divide them by (st) 2 , since it is always a factor and we let H 1 (s, t), H 2 (s, t) ∈ Z[s, t] be their numerators respectively. We now have to compute the isolated roots of the system {H 1 (s, t) = H 2 (s, t) = 0} over R 2 . This system has as roots also the tuple of parameters that correspond to multiple points of the curve and the tuples of poles. The pairs that correspond to multiple points can be viewed as bitangents of length zero, and thus do not harm the correctness of the algorithm. As for the pairs of poles, they can easily be excluded, by checking if any parameter is also a root of q 1 (s) • q 2 (s). For the segments of types IV and V, that have an endpoint of the form ϕ(a), with a ∈ bd(I), we isolate the roots of H 1 (s, a) ∈ Q[s] and we consider all the pairs (s, a) such that s is a root of H 1 (s, a). For segments of type VI we just have to consider all pairs of parameters in bd(I). In that way, we can construct the set S, containing all the pairs of parameters.

Step 2: Decomposition of the curve. We subdivide I into a finite number of open intervals and points, where the points of the decomposition are the parameters of all pairs in S. Let R t (s) = res t (H 1 , H 2 ). The points of the decomposition are roots of the polynomial

P(s) := R t (s) a∈bd(I) (s -a) • H 1 (s, a) . (5)
Now, every sub-interval corresponds to a parametric arc that does not contain endpoints of any segment and thus, it is either contained in the boundary of conv(ϕ(I)) or in its interior.

Step 3: Computing the arcs. For every interval I j of the decomposition of I computed in

Step 2, we work as follows: We pick any rational u ∈ I j ; ϕ(u) is always a smooth point on C since the singular points are given by parameters that are among the points of decomposition of I. We check if ϕ(u) is on the boundary of conv(ϕ(I)), which is the case if and only if there is a supporting line of ϕ(I) passing from ϕ(u) [START_REF] Brøndsted | An Introduction to Convex Polytopes[END_REF]Thm.4.3]. But since ϕ(u) is smooth, the only possible supporting line is the tangent line to C at ϕ(u). So we call the predicate Support for the tangent line at ϕ(u).

Its equation is ⟨(x, y) -ϕ(u), (-ϕ ′ 2 (u), ϕ ′ 1 (u)⟩ = 0 . Let ℓ u (λ) ∈ Q[λ]
be the numerator of the tangent line equation after substituting (x, y) with the parametrization ϕ(λ). We isolate the real roots of ℓ u (λ) in order to determine its sign in I. If it is supporting to ϕ(I), then the parametric arc ϕ(I j ) is on the boundary of conv(ϕ(I)).

Step 4: Connecting the facets. Having determined the curved facets on the boundary at the previous step, we now describe how they connect with each other. In other words, we compute the segments, among the ones found in the first step, that are on the boundary of the convex hull. Two neighboring facets, intersect at a point of the curve. Since this point is on the boundary, there has to be a supporting line to the curve passing from it [START_REF] Brøndsted | An Introduction to Convex Polytopes[END_REF]Thm.4.3]. If it is a smooth point, then the supporting line can only be the tangent line. When the point is not smooth, there is not a unique possible choice for the supporting line. So, for every arc of the curve that is on the boundary, we check each of its endpoints:

• If the endpoint is smooth, then the parametric arc is adjacent to the bitangent segment passing from this point.

• If the endpoint is not smooth but it belongs to a segment that has only one non-smooth point, then, the segment will be found with this procedure from the other one of its two adjacent curved facets.

• If the endpoint is not smooth and it belongs to a segment with two non-smooth endpoints, that is cusp-cusp (type III), endpoint-cusp (type IV) and endpoint-endpoint (type V) segment, we need to check every possible combination to find the ones that contribute to the boundary. Thus, for every such segment we check if it lies on a supporting line to the curve by calling the predicate Support. The parameters corresponding to cusp-cusp segments are also among the solutions of the system {H(s) = H(t) = 0}. The equation of the line passing through ϕ(s) and ϕ(t

) is ⟨ϕ(s) -(x, y), (-(ϕ 2 (s) -ϕ 2 (t)), (ϕ 1 (s) -ϕ 1 (t))⟩ = 0 .
We substitute (x, y) with ϕ(λ) in the previous equation. Let L(s, t, λ) ∈ Z[s, t, λ] be the polynomial obtained after clearing the denominators . Calling the predicate Support for all the lines connecting cusps, amounts to computing the isolated roots of

H(s) = 0 , H(t) = 0 , L(s, t, λ) = 0 . (6)
For the segments of type V, for all a ∈ bd(I), we compute the polynomial L(a, t, λ) ∈ Q[t, λ] and then solve the system {H(t) = L(a, t, λ) = 0}. For the endpoint-endpoint segments, we solve for λ the polynomials L(a, b, λ) ∈ Q[λ] for every a, b ∈ bd(I).

Complexity analysis. The following definition serves in expressing the bit-complexity.

Definition 3. We consider the zero-dimensional polynomial system The correctness of the algorithm is based on the fact that the Support predicate, correctly detects the curve branches that are on the boundary of the convex hull (Step 3). On connecting the curve branches with segments, we refer to the selection criterion of the gift-wrapping algorithm for the set of points ϕ(I); given a point p on the boundary of the convex hull, the next point with whom it connects, is a point q ∈ ϕ(I) such that the line that passes from p and q is strictly supporting for the convex hull. The connection phase in Step 4 respects this criterion.

{F 1 (X 1 ) = • • • = F N (X N ) = F(X 1 , . . . , X N , Y) = 0} in Z[X 1 , . . . , X N , Y]. If
Remark 6 (Degeneracies). In a degenerate situation, several line segments on the boundary of the convex hull can lie on the same supporting line (e.g., Fig. 2). Consequently, each segment will be accounted for multiple times with different pairs of endpoints. However, this problem can be resolved during a post-processing stage, where the systems' solutions from the first step are analyzed to identify such situations.

Bit-complexity

Step 1. We compute the polynomials H Isolating the isolated roots of the system {H 1 (s, t) = H 2 (s, t) = 0} costs O B (d 6 + d 5 τ) [START_REF] Kobel | On the complexity of computing with planar algebraic curves[END_REF]. If it is not zero-dimensional, then we have first to compute the gcd of H 1 and H 2 and their gcd-free parts. This is done in O B (d 6 + d 5 τ). We can also compute the resultant of H 1 and H 2 with respect to s or t at no extra cost. Notice that both resultants are the same polynomial, since the system is symmetric. Let R t (s) = res Step 2. We decompose I at the endpoints of all the segments, which are roots of the polynomial P (Eq. ( 5)). Every endpoint is approximated by an isolating interval, so what it suffices, is that for two consecutive parameters in the sorted list, the respective isolating intervals do not overlap. The polynomial P is of size (O(d 2 ), O(dτ)) and we find isolating intervals of its roots in O B (d 6 + d 5 τ) [START_REF] Mehlhorn | From approximate factorization to root isolation with application to cylindrical algebraic decomposition[END_REF]Thm. 5]. Every endpoint of an isolating interval is a rational of size O(σ i ), and for all of them the bitsizes sum to O(d 3 τ).

Step 3. We take a rational inside every interval of the decomposition, say u i with i = 1, . . . , O(d 2 ). The sum of their bitsizes is again in O(d 3 τ). For every u i , [START_REF] Mehlhorn | From approximate factorization to root isolation with application to cylindrical algebraic decomposition[END_REF]Thm. 5]. In the same bit-complexity we can decide if ℓ u i (λ) is non-negative in I. Summing for all i we get a total bit-complexity in O B (d 6 τ).

ℓ u i (λ) ∈ Q[λ] is a polynomial of size (d, O(dσ i + τ)), so we isolate its roots in O B (d 3 σ i + d 2 τ)
Step 4. To keep only the zero dimensional part of the solutions of the system in Eq. ( 6 [START_REF] Bouzidi | Improved algorithms for solving bivariate systems via rational univariate representations[END_REF]Lem. 4]. Analogously, we compute the gcd of R t 0 (t), . . . , R t D (t), H(t) and we let ht (t) be the gcd-free part of the last polynomial. Then, the system { hs (s) = ht (t) = L(s, t, λ) = 0} is zero-dimensional and gives the isolated solutions of the system in Eq. ( 6). The bit-complexity of isolating its roots is C(d, d + τ, 2).

Examining the multiplicities of the roots, allows to find the pairs (s 0 , t 0 ) for whom L(s 0 , t 0 , λ) is sign-invariant in I, and therefore decide which segments are on the boundary of the convex hull. For the segments of type V, for all a ∈ bd(I), we compute the polynomial L(a, t, λ) and then solve the system {H(t) = L(a, t, λ) = 0}. Since the number of boundary points is assumed to be in O(1), this cost is C(d, τ, 1). Step 4 requires also manipulating the output data structure; we perform O(d 2 ) updates, each one in constant time.

So, it total the bit-complexity of the algorithm is in O

B (d 7 + d 6 τ) + C(d, d + τ, 2).

Output of the algorithm

The output is circular doubly linked list L; this data structure consists of a sequence of records, each one corresponding to a facet of the convex hull. Every record contains the data required to describe the facet and a link to a previous and a next record. The data is a parameter interval, say [t 1 , t 2 ], together with a parametrization; the image of the interval over the 10 parametrization is an arc of ϕ(I) or a segment on the boundary of conv(ϕ(I)). The link to the previous record points to the neighboring facet containing ϕ(t 1 ), and the link to the next record points to the neighboring facet containing ϕ(t 2 ). Note that the intervals that are contained in the data of each record are all bounded sub-intervals of I, except from at most one which may be of the form (-∞, a] ∪ [b, +∞) (Rem. 1).

For the size of the output, we have that N ∈ O(d 2 ) by taking into account the degrees of the systems entailed in the computation of segments of the different types and Assumption 4(ii).

Remark 7. If the curve is smooth, without self-intersections, we have that N ∈ O(d). [START_REF] Elber | The convex hull of rational plane curves[END_REF]; this is since there are O(d) inflection points and poles. If there is a bitangent connecting two smooth points ϕ(t 1 ), ϕ(t 2 ) with t 1 < t 2 then in the interval [t 1 , t 2 ], there exists at least one parameter that corresponds to an inflection point or a pole. Moreover, since there are O(d) cusps, the number of Type II and III segments that are on the boundary of the convex hull is also in O(d). The segments of Type IV, V, VI are already in O(1) (Assumption 4(ii)).

Convex hull of parametric curves in R 3

Now ϕ(t) = (ϕ 1 (t), ϕ 2 (t), ϕ 3 (t)) = p 1 (t) q 1 (t) , p 2 (t) q 2 (t) , p 3 (t) q 3 (t) is defined as in Eq. ( 1). We make again the simplifying Assumptions 4 of Sec. 4. The facets of the convex hull are triangles with vertices points on the curve. In addition, it includes one-dimensional families of segments with endpoints on the curve, which are one-dimensional faces. These families assemble to two-dimensional surface patches, to which we refer from now on as facets, with abuse of terminology. The next definition classifies the triangles on the boundary of the convex hull in several types (see Fig. 5 and Rem. 14). Definition 8. We distinguish the following types of triangles on the boundary of conv(ϕ(I)) according to their vertices: I. tangent triangles: there is at least one vertex that is a smooth point of C and the triangle lies on a tangent plane to C at this point. The other two vertices of the triangle are either smooth points, at which the plane is also tangent, or cusps, II. cuspidal triangles: the three vertices of the triangle are cusps, III. endpoint triangles: there is at least one vertex of the triangle that is given by a parameter in bd(I).

The one-dimensional families of segments on the boundary of the convex hull form developable surface patches, that can be also classified (see Fig. 6). Definition 9. We distinguish the following types of surface patches according to the vertices of the spanning segments:

I. bitangent surface patches: the segments' endpoints are smooth points of C and the segment lies on the plane tangent to the curve at these two points, II. cuspidal surface patches: all segments have a common endpoint that is a cusp, III. endpoint surface patches: all segments have a common endpoint that is given by a parameter in bd(I).

The pairs of parameters that give these type of segments, are points of a plane curve. Let E(s) := a∈bd(I) (sa). We define the bisecant curve as the zero set of the equation

G(s, t) := det(ϕ(s) -ϕ(t), ϕ ′ (s), ϕ ′ (t)) • E(s) • E(t) (s -t) 4 = 0 . (7)
We divided by (st) 4 since it is a factor of the numerator. We multiplied by both E(t) and E(s) to preserve the symmetry. A point (s, t) ∈ R 2 satisfying Eq. ( 7) is such that:

• ϕ(s) -ϕ(t), ϕ ′ (t), ϕ ′ (s) 0 and there is a bitangent plane to C at ϕ(s) and ϕ(t), or • ϕ(s) = ϕ(t) and/or ϕ ′ (t) = 0 and/or ϕ(s) = 0, i.e., ϕ(t) is a multiple point and/or ϕ(t) is a cusp and/or ϕ(s) is a cusp, or

• s ∈ bd(I) or t ∈ bd(I). Now, we consider all the segments ϕ(s)ϕ(t), with s and t satisfying G(s, t) = 0. This gives rise to the bisecant surface in R 3 :

B = T ϕ(s) + (1 -T ) ϕ(t) | T ∈ [0, 1], G(s, t) = 0 . ( 8
)
The bisecant surface is ruled, since through every point of the surface there is a straight-line segment that lies on it, and it is also developable [3, §5.1]. The surface patches of Def. 9 are part of this surface. Only certain parts of the bisecant surface are on the boundary of the convex hull. We will use the bisecant curve to find and describe these parts.

Algorithm

Step 1: Computing the triangles. We compute all triangles of types I to III for ϕ(I). Each triangle has a type (I to III) and is determined by three parameter values, say a, b and c, such that ϕ(a), ϕ(b) and ϕ(c) are the triangle's vertices. We find the parameters that correspond to each type of triangles by solving a polynomial system and we denote by S the set of all such triples. We assume that for a given triple of parameters in S we can determine the type of the corresponding triangle in constant time. To find the different types of triangles, it is easier to factorize G (Eq. ( 7)) and consider each type separately. We know that cusps of C are given by parameters that are among the roots of H(s) (Eq. ( 3)). So, in the case where there are cusps, the polynomial G can be factorised as Ĥ(s)

• Ĥ(t) • Ĝ(s, t) • E(s) • E(t)
, where Ĥ corresponds to the parameters that give cusps. We consider the equations in Z(s, t, u):

det(ϕ(u) -ϕ(t), ϕ ′ (t), ϕ ′ (s)) (s -t)(t -u) 2 = 0 , (9)
det(ϕ ′ (s), ϕ ′ (t), ϕ ′ (u)) (s -t)(t -u)(s -u) = 0 . ( 10
)
Let (s, t) ∈ R 2 such that Ĝ(s, t) = 0. Then, ϕ(s) and ϕ(t) are both smooth points, since we have excluded the factors that correspond to cusps. Let P be the common tangent plane passing from ϕ(s) and ϕ(t). Then, Eq. ( 9) expresses the fact that the plane P intersects the curve at ϕ(u). Eq. ( 10) expresses the condition that the three tangent vectors, ϕ ′ (s), ϕ ′ (t), and ϕ ′ (u) lie on the same plane and so P is also tangent to

C at ϕ(u), if it is smooth. Let H 1 , H 2 ∈ Z[s, t, u]
be the numerators of Eq. ( 9) and Eq. ( 10) respectively. From the isolated roots of the system { Ĝ = H 1 = H 2 = 0} we can obtain the tangent triangles with three or two smooth vertices (when ϕ(u) is a cusp). We consider the equations in Z(s, t, u):

det(ϕ(u) -ϕ(s), ϕ(u) -ϕ(t), ϕ ′ (u)) (t -u) 2 (s -u) 2 (s -t) = 0 , det(ϕ(u) -ϕ(s), ϕ(u) -ϕ(t), ϕ ′ (s)) (t -u)(s -u) 2 (s -t) 2 = 0 .
Let H 3 , H 4 ∈ Z[s, t, u] be their numerators respectively. For the tangent triangles with one smooth vertex and two cusps, we solve the system:

H(s) = 0 , H(t) = 0 , H 3 (s, t, u) = 0 . (11)
The system has also as roots the parameters corresponding to cuspidal triangles, since ϕ(u) can be a cusp. For the endpoint triangles, for every a ∈ bd(I), to find the planes that go through it, we solve the system

H 1 (s, t, a) = 0 , H 4 (s, t, a) = 0 . ( 12
)
For any a, b ∈ bd(I), to find the planes that go through ϕ(a), ϕ(b), we solve the equation Step 2: Decomposition of the bisecant curve. We consider the graph of G and we compute a special purpose Cylindrical Algebraic Decomposition (CAD) of the s-axis. In a CAD we decompose the s-axis into a finite number of points and open intervals delimited by these points over which the graph of the bisecant curve G has a cylindrical structure, i.e., the number of branches of the graph of the curve is constant. We call the points defining the decomposition special values. Special fibers are the points on the curve above the special values. Regular fibers are the points on the curve above additional points between two special values.

H 4 (s, a, b) = 0 . (13) 13
In a CAD the special values are the projections of the s-critical points and the vertical asymptotes. We refine the decomposition by further subdividing the intervals at the projections of the t-critical points and at the parameters of all triples corresponding to the triangles computed in the previous step. Let (s 0 , t 0 ) be a point on the graph of G, such that the line segment connecting ϕ(s 0 ) and ϕ(t 0 ) is on the boundary of the convex hull and is on a bisecant surface patch. If we move along the arc of the graph of G around the point (s 0 , t 0 ) and we take a neighboring point (s ′ , t ′ ) that is sufficiently close, then, the segment ϕ(s ′ )ϕ(t ′ ) is also on the boundary of the convex hull, part of the same bisecant surface patch (see Fig. 7). In particular, by moving along the arc in both directions starting from (s 0 , t 0 ), we get bitangent segments that are on the bisecant surface patch, and thus, obtain a way to trace it. We continue until we find point (s ′′ , t ′′ ) that corresponds to a segment that is on the intersection of the bisecant surface patch with another facet. This point can be such that:

• ϕ(s ′′ ) and ϕ(t ′′ ) are vertices of triangle (so, s ′′ and t ′′ are both special values of the decomposition), or

• (s ′′ , t ′′ ) is a self-intersection point of G, i.e.
, there are two surface patches that intersect at the segment with endpoints ϕ(s ′′ ) and ϕ(t ′′ ). So, in this case s ′′ is an s-critical point and therefore a special value of the decomposition.

All the previous discussion suggests that an arc of the decomposition of G (that is obtained by the decomposition of the s-axis) corresponds to a surface patch that is either on the boundary of the convex hull or in its interior.

Step 3: Computing the bisecant surface patches. We want to find the arcs of G that correspond to the bisecant surface patches on the boundary of the convex hull. The following lemma gives a criterion. It is a direct consequence of the discussion in Step 2.

Lemma 10. We consider a smooth and monotonous arc on the graph of G, with A = (s 1 , t 1 ) and B = (s 2 , t 2 ) its endpoints. If there is no point on the arc that corresponds to a bitangent segment belonging on a triangle, then, if any interior point on the arc corresponds to a bitangent segment on the boundary of the convex hull then the entire arc corresponds to a bitangent surface patch on the boundary of the convex hull.

Over every open interval of the decomposition of the s-axis there are several arcs of the graph of G, corresponding to bitangent surface patches. From Lem. 10, in order to determine if a patch is on the boundary it suffices to take an interior point of the arc and check if the corresponding tangent plane is supporting for ϕ(I), using the Support predicate.

For every (open) interval I j of the decomposition, we work as follows: We pick any rational u ∈ I j and we solve G(u, t) = 0. For every v such that G(u, v) = 0, we have that ϕ(u) and ϕ(v) are always smooth points on C since the singular points are given by parameters that are among the points of decomposition of the s-axis. We check if the segment connecting ϕ(u) and ϕ(v) is on the boundary of conv(ϕ(I)), which is the case if and only if there is a supporting plane of ϕ(I) passing from ϕ(u) and ϕ(v). But since both points are smooth, the only possible supporting plane is the tangent plane to C at ϕ(u) and ϕ(v). So we call the predicate Support for this plane.

Its equation is det((x, y, z) -ϕ(u), ϕ ′ (u), ϕ ′ (v)) = 0 . Let ℓ u,v (λ) ∈ Q[λ]
be the numerator of the tangent line equation after substituting (x, y) with the parametrization ϕ(λ). We isolate the real roots of ℓ u,v (λ) in order to determine its sign in I. If the plane is supporting to ϕ(I) then the arc of G over I j , containing the point (u, v), corresponds to a bisecant surface patch that is on the boundary of conv(ϕ(I)).

Step 4: Connecting the facets. Having determined the bisecant surface patches on the boundary at the previous step, we now describe how they connect with each other. In other words, we compute the triangles, among the ones found in the first step, that are on the boundary of the convex hull. Two neighboring facets intersect at a line segment with endpoints that are points on the curve. Let ϕ(s) and ϕ(t) be the endpoints of such a segment. Since this segment is on the boundary, there has to be a supporting plane to the curve containing it. If at least one point is smooth, then the supporting plane can only be the plane tangent to the curve at the smooth point and passing from both. If none of the points is smooth, then the supporting plane is not uniquely defined. So, for every arc of the graph of G corresponding to a bisecant surface patch on the boundary, we check each of its endpoints. Let (s, t) be one of them.

1. If at least one of ϕ(s) and ϕ(t) is a smooth point, say ϕ(s), then the plane that is tangent to C at ϕ(s) and passes from ϕ(t) is uniquely defined. This plane passes from a third point ϕ(u) on C, that was found in Step 1. So, there is only one possible plane facet (if there are no degeneracies) that is neighboring, and this is the triangle with vertices ϕ(s), ϕ(t) and ϕ(u). In a degenerate situation, there will be more than one u, corresponding to the multiple interections of the plane with the curve, and the different triangles that belong on the same plane will be considered multiple times (see Rem. 13). 2. If both ϕ(s) and ϕ(t) are cusps or endpoints of ϕ(I), then we need to check every possible combination in order to find the triangle containing this segment that is on boundary. For the cuspidal triangles, let (s, t, u) ∈ R 3 be a triple of parameters corresponding to cusps. Then, ⟨(ϕ(s) -ϕ(u)) × (ϕ(s) -ϕ(t)), ϕ(s) -(x, y, z)⟩ = 0 is the implicit equation of the plane in R 3 that goes through ϕ(s), ϕ(t) and ϕ(u). We substitute (x, y, z) with ϕ(λ) in the previous equation. Let L(s, t, u, λ) ∈ Z[s, t, u, λ] be the polynomial obtained after clearing Remark 13 (Degeneracies). In a degenerate situation, several triangles on the boundary of the convex hull can lie on the same supporting plane (e.g., Fig. 11) or several surface patches can be included in a bigger surface patch. Consequently, each boundary element will be accounted for multiple times. However, this problem can be resolved during a post-processing stage, where the systems' solutions from the first step are analyzed to identify such situations.

Remark 14. If we consider all the possible combinations of the three vertices of a triangle (smooth point, cusp, endpoint), we see that there exist ten different configurations. Among them, three correspond to tangent triangles, to cuspidal triangle and six to endpoint triangles. We divide them in the three categories of Def. 8 due to the following reasons:

• To define uniquely a plane that passes from a smooth point of C and is tangent to the curve at this point, we need to specify another point belonging on the plane. Therefore, the plane in which the tangent triangle belongs is not affected by the smoothness (or not) of the two other vertices.

• The cuspidal and endpoint triangles can be obtained as solutions of a polynomial system of special structure, which is simpler comparing to the system corresponding to tangent triangles.

Bit-complexity

Step 1. We construct the polynomials [START_REF] Daouda | Bounds for polynomials on algebraic numbers and application to curve topology[END_REF]Prop. 21], by considering G(s, t) as a polynomial in s or in t and then finding the gcd of the coefficients.

G, H 1 , H 2 , H 3 , H 4 in O B (d 3 τ) [44, Ch. 8]. We factorize G as Ĥ(s) • Ĥ(t) • Ĝ(s, t) • E(s) • E(t) in O B (d 4 + d 3 τ)
To find the triangles with two or three smooth vertices we need to find the isolated roots of the system { Ĝ(s, t) = H 1 (s, t, u) = H 2 (s, t, u) = 0}. In particular, we are only interested in the first two coordinates of the roots; if (a, b, c) is a solution to the system and ϕ(u) is smooth, then all the possible permutations of a, b, c are solutions as well. So, we can obtain the triples corresponding to tangent planes with smooth vertices just by the (s, t)-projections. We take the resultant [START_REF] Kobel | On the complexity of computing with planar algebraic curves[END_REF] (if the system is not zero-dimensional we first compute the gcd and the gcdfree parts).

Tangent triangles with two smooth vertices can be found by computing the isolated roots of the system { Ĝ(s, t) = H(u) = H 1 (s, t, u) = 0}. In particular, we are only interested this time in the last two coordinates of the roots; if (a, b, c) is a solution to the system and ϕ(a), ϕ(b) are smooth, then (b, a, c) is a solution as well. Thus, we can group the triples corresponding to the same triangle. The resultant R 3 (s, u)

:= res t ( Ĝ, H 1 ) ∈ Z[s, u] is of size (O(d 2 ), O(dτ)) and is computed in O B (d 7 τ). We isolate the roots of {H(u) = R 3 (s, u) = 0} in O B (d 8 + d 7 τ).
For the triangles with one smooth point and the cuspidal triangles, we find the isolated roots of the system of Eq. [START_REF] Cucker | On the mathematical foundations of learning[END_REF] in O B (d 7 + d 6 τ) in the same way as for the system in Eq. [START_REF] Bouzidi | Separating linear forms and rational univariate representations of bivariate systems[END_REF].

At last, for every a ∈ bd(I), we compute H 1 (s, t, a) and Step 2. The decomposition points of the s-axis are:

• s-projections of critical points of G, and thus roots of res t (G, ∂G/∂t). The graph of G is symmetric with respect to the line s = t, so we do not consider also res t (G, ∂G/∂s),

• The s-values where vertical asymptotes occur. These values are roots of the leading coefficient of G(s, t), considered as a polynomial in t,

• parameters corresponding to a triangle, and thus roots of

H(s) • R 2 (s) a∈bd(I)         (s -a) • res t (H 1 (s, t, a), H 4 (s, t, a)) b∈bd(I) H 4 (s, a, b)         .
The product of these polynomials is of size (O(d 3 ), O(d 2 τ)). We isolate its roots in O B (d 9 + d 8 τ) [START_REF] Mehlhorn | From approximate factorization to root isolation with application to cylindrical algebraic decomposition[END_REF]Thm. 5]. Every endpoint of an isolating interval is a rational of size O(σ i ), and for all of them the bitsizes sum to O(d 5 τ).

Step 3. We take a rational point q i inside every interval of the decomposition (e.g. the midpoint); it has bitsize O(σ i ). We construct the polynomial G(q i , t) by performing O(d) evaluations of univariate polynomials at q i . Then, calling the predicate Support for every intersection point on the graph of G, amounts to isolating the roots of the system G(q i , t) = 0 H 1 (t, q i , λ) = 0 This costs C(d, dσ i , 1). Summing for all i, since C is linear in the bitsize, we obtain C(d, d 6 τ, 1).

Step 4. To keep only the zero dimensional part of the solutions of the system in Eq. ( 14) we work as follows: Let L(s, t, u, λ) = l D (s, t, u)λ D + • • • + l 1 (s, t, u)λ + l 0 (s, t, u), where D = O(d). For i = 1, . . . , D, we compute [START_REF] Bouzidi | Improved algorithms for solving bivariate systems via rational univariate representations[END_REF]Lem. 4]. Then, the system { hs (s) = ht (t) = hu (u) = L(s, t, u, λ) = 0} is zero-dimensional and gives the isolated solutions of the system in Eq. ( 14). The bit-complexity of isolating its roots is C(d, d + τ, 3). Computing the isolated roots of the other systems in this step is dominated by the previous computations.

R s i (s) = res u (res t (l i (s, t, u), H(t)), H(u)) ∈ Z[s] , R t i (t) = res u (res s (l i (s, t, u), H(s)), H(u)) ∈ Z[t] , R u i (u) = res t (res s (l i (s, t, u), H(s)), H(t)) ∈ Z[u] .
So, the bit-complexity of the algorithm is in

O B d 10 + d 9 τ + C(d, d 6 τ, 1) + C(d, d + τ, 3) .

Output of the algorithm

We will use the half-edge data structure, or doubly connected edge list (DCEL), to represent the output [12,Ch.2.2]. This data structure is used to represent an embedding of a planar graph in the plane by maintaining the following records: vertices, edges and faces. By extension, it is widely used to describe the boundary of three-dimensional convex polyhedra and is also convenient to describe the boundary of the convex hull of ϕ(I). In our case, a face is a 2-dimensional facet of the convex hull, that can be either a triangle or a bisecant surface patch. An edge is intersection of two facets, i.e, a parametric arc or a segment connecting two points of the curve. A vertex is the intersection of two edges of the convex hull, i.e., a point on the curve.

The principle of this data structure is to 'decompose' every edge into two half-edges with opposite directions. All the records are associated to a half-edge and this allows to encode all the combinatorial information of the planar graph, or of the boundary of the convex hull in the present case. In particular:

• a vertex is associated to one (arbitrary) halfedge with the vertex as starting point,

• an edge is associated to one halfedge,

• a face is associated to some halfedge on its boundary,

• a halfedge is associated to the vertex that is its origin, to a "twin" halfedge, that is the halfedge with the opposite direction, and to the face that is incident to the edge on the left side, when we traverse it from the origin to its endpoint.

Although it is a combinatorial data structure, we can also store geometrical information on the records, by giving them extra attributes:

• For a vertex, since it a point on the curve, we store the corresponding parameter,

• For an edge, if it is a parametric arc we store the corresponding parameter interval. If it is a bitangent segment, it is described by the two parameters that correspond to the endpoints of the segment,

• A face can be either a triangle or a bisecant surface patch. In the first case, it is described by the parameters of the incident vertices. In the second case, it is described by the reference to its corresponding arc of the graph of G. An arc is described by its endpoints, its projection on the s-axis and its ordering with respect to other branches over the interval.

For the number of the facets on the boundary of the convex hull, we consider the degrees of the systems entailed in the computation of triangles and Assumption 4(ii).

Implementation and Examples

We provide some examples using our prototype implementation in Maple. It is built upon the real root isolation routines of Maple's RootFinding library and the PTOPO package [START_REF] Katsamaki | PTOPO: A Maple package for the topology of parametric curves[END_REF], to compute the topology and visualize parametric curves in two and three dimensions. .

The parametrization is proper. We take I = R. We compute the polynomials We isolate the real roots of the system {H 1 = H 2 = 0}; they correspond to the blue segments in Fig. 8(a). Then R is decomposed at the s-projections of the roots (Fig. 9). The segments on the boundary of the convex hull are shown in red in Fig. 8(b) and the parameter intervals corresponding to the arcs on the boundary of conv(ϕ(R)) are annotated in orange in Fig. 9. Example 16. We consider a curve in R 3 parametrized by ϕ(t) = -(t + 3)(3t -1) 5(t 2 + 1) , 2(t -2)(2t + 1) 5(t 2 + 1) , 8(t -2)(2t + 1)(t + 3)(3t -1)(7t 2 + 2t -7)(t 2 -14t -1) 625(t 2 + 1) 4 .

The parametrization is proper. We take I = R. The bisecant curve is defined by: G(s, t) =64 (5s 2 t 2s 2 + 12stt 2 + 5)(17s 2 t 2 + 62s 2 t + 62st 2 -17s 2 -68st -17t 2 -62s--62t + 17) • (31s 2 t 2 -34s 2 t -34st 2 -31s 2 -124st -31t 2 + 34s + 34t + 31) .

The curve has neither cusps nor endpoints. We compute H 1 , H 2 and R 1 = res u (H 1 , H 2 ) and we solve the system {G = R 1 = 0}. There are 96 real roots. For simplicity, in Fig. 10 Example 17. We consider the curve in R 3 parametrized by ϕ(t) = -3t 2 -1 t 2 + 1 , -t (3t 2 -1) (t 2 + 1) 2 , -(t 6 -1)(3t 2 -1) (t 2 + 1) 4 .

The parametrization is proper. We take I = R. The bitangent curve is defined by: G(s, t) = -8(s + t)(63s 7 t 7 + 81s 7 t 5 -33s 6 t 6 + 81s 5 t 7 + 45s 7 t 3 -159s 6 t 4 -201s

Figure 1 :

 1 Figure 1: (a) A plane curve and its convex hull; the boundary consists of the green line segments and the orange arcs. (b) A curve in R 3 and its convex hull; the boundary consists of one triangle and four ruled (developable) surface patches (in red and in blue).

Figure 2 :

 2 Figure 2: (a) The graph of the curve parametrized by -t 2 +1t 2 +1 , -8t(t 2 -1)(t 4 -6t 2 +1) t 8 +4t 6 +6t 4 +4t 2 +1 , (b) segments tangent to the curve at two points or more (in blue), (c) the ones that are on the convex hull (in red).

Figure 3 :

 3 Figure 3: The line ⟨a, x⟩ + c = 0 is supporting for ϕ(I); ϕ(I) lies entirely in the halfplane where ⟨a, x⟩ + c is positive. The line segment (in red) is on the boundary of the convex hull.

Figure 4 :

 4 Figure 4: Segments of type (a) I, (b) III and (c) IV and VI (in blue).

Corollary 5 .

 5 all the polynomials have degree O(M) in each variable and bitsize in O(Λ), then C(M, Λ, N) is the bit-complexity of computing isolating intervals for the roots. C(M, Λ, N) is linear in Λ and is increasing with N.The next theorem summarizes our result. Its proof follows in the next subsection.Theorem 4. Let C be a curve with a proper parametrization ϕ(t) as in Eq. (1), of size(d, τ). Let I ⊂ R such that ϕ(I) is compact in R 2 .There is an algorithm that computes the convex hull of ϕ(I) in O B (d 7 + d 6 τ) + C(d, d + τ, 2). The output of the algorithm is a circular doubly linked list (with N ∈ O(d 2 ) elements), containing the parameter intervals and the corresponding parametrizations for each facet; the image of the interval over the parametrization is a parametric arc or a segment on the boundary of conv(ϕ(I)). Using the bit-complexity results of[START_REF] Katsamaki | On isolating roots in a multiple field extension[END_REF] for C(d, d + τ, 2), the bit-complexity of the previous theorem becomes O B (d 10 + d 9 τ).

1 ,

 1 H 2 in O B (d 3 + d 2 τ): To construct the numerator of each H i we perform multiplications of univariate polynomials in the variable s and in the variable t; this costs O B (d 2 τ) [44, Ch.8]. The bi-degree of the resulting expression is in (O(d), O(d)) and its bitsize in O(τ). Then, we divide by (st) 2 and this costs O B (d 3 + d 2 τ) by adapting [44, Ex.10.21] to the bivariate case. The polynomials H 1 and H 2 are then of size (O(d), O(d + τ)).

  t (H 1 , H 2 ). It is of size (O(d 2 ), O(d 2 + dτ)) [2, Prop. 8.46]. For the segments of types IV-V, for every a ∈ bd(I), we construct the polynomial H a (t) by performing O(d) evaluations of polynomials of size (O(d), O(d + τ)) at a in O B (d(d + τ)) [6, Lem. 6]. Then we isolate its roots in O B (d 3 + d 2 τ) [32, Thm. 5].

  ) we work as follows: Let L(s, t, λ) = l D (s, t)λ D + • • • + l 1 (s, t)λ + l 0 (s, t), where D = O(d). For i = 1, . . . , D, we compute R s i (s) = res t (l i (s, t), H(t)) and R t i (t) = res s (l i (s, t), H(s)) in O B (d 5 τ) [29, Lem. 4]. We compute the gcd of R s 0 (s), . . . , R s D (s) in O B (d 7 + d 6 τ) [24, Lem. 2] and then the gcd of the later with H(s) in O B (d 3 τ) [5, Lem. 4]. Let hs (s) the gcd-free part of H(s). It has bitsize O(d+τ)

Figure 5 :

 5 Figure 5: In green (a) a tangent triangle, (b) a cuspidal triangle and (c) an endpoint triangle.

Figure 6 :

 6 Figure 6: (a) A bitangent surface patch, (b) a cuspidal surface patch, (c) an endpoint surface patch.

Figure 7 :

 7 Figure 7: (a) An arc of the graph of the bisecant curve G and (b) the surface patch that corresponds to the part of the arc between (s 0 , t 0 ) and (s ′ , t ′ ) (in purple).

  R 1 (s, t) := res u (H 1 , H 2 ) ∈ Z[s, t]. It is a polynomial of degree O(d 2 ) in each variable and bitsize in O(dτ) [2, Prop. 8.72]. It is computed in O B (d 7 τ). Then, we consider the system { Ĝ = R 1 = 0}. We take the resultant R 2 (s) := res t ( Ĝ, R 1 ) ∈ Z[s]. It is of size O(d 3 ), O(d 2 τ)) [26, Cor. 5] and is computed in O B (d 8 τ) [26, Lem. 6]. At last, we isolate the roots of {R 2 = Ĝ = 0} in O B (d 9 + d 8 τ)

  H 4 (s, t, a) by performing O(d 2 ) evaluations at a; this costs O B (d 3 τ) and the resulting polynomials have bitsize in O(d + τ) [6, Lem.7]. Then, we solve the bivariate systems of Eq. (12) in O B (d 6 + d 5 τ). For all a, b ∈ bd(I), we compute H 4 (s, a, b) (Eq. (13)) in O B (d 3 τ) [6, Lem.7]. These polynomials have bitsize in O(d + τ) and so we isolate the roots in O B (d 3 + d 2 τ) [32, Thm. 5].

Figure 8 :

 8 Figure 8: (a) The curve of Example 15 (in green) and the segments computed at the first step of the algorithm (in blue). (b) The segments on the boundary of the convex hull (in red).

Example 15 . 3 ,

 153 We consider a curve in R 2 parametrized byϕ(t) = -2 12t 2 + 7t -12 1679t 4 + 2688t 3 -5074t 2 -2688t + 1679 15625 t 2 + 1 (t -7) (7t + 1) 2929t 4 + 2688t 3 -2574t 2 -2688t + 2929 15625 t 2 + 1 3

H 1 (

 1 s, t) =128092t 4 s 4 + 86016t 3 s 4 + 43008t 4 s 3 -159912t 2 s 4 + 292544t 3 s 3 -25000t 4 s 2 --43008t s 4 + 43008t 2 s 3 + 129024t 3 s 2 + 34364s 4 -187456t s 3 + 265264t 2 s 2 --187456t 3 s + 34364t 4 -129024t s 2 -43008t 2 s + 43008t 3 -25000s 2 + + 292544st -159912t 2 -43008s -86016t + 128092 , H 2 (s, t) = -128092t 4 s 4 -43008t 3 s 4 -86016t 4 s 3 + 25000t 2 s 4 -292544t 3 s 3 + 159912t 4 s 2 --129024t 2 s 3 -43008t 3 s 2 + 43008t 4 s -34364s 4 + 187456t s 3 -265264t 2 s 2 + + 187456t 3 s -34364t 4 -43008s 3 + 43008t s 2 + 129024t 2 s + 159912s 2 --292544st + 25000t 2 + 86016s + 43008t -128092 .

Figure 9 :

 9 Figure 9: Decomposition of the parameter interval in Example 15.

Figure 10 :

 10 Figure 10: (a) The graph of the bisecant curve of Example 16. (b) The arcs of the bisecant curve that correspond to bisecant surface patches are shown in orange.

Figure 11 :

 11 Figure 11: (a) The bisecant surface and (b) the convex hull of the curve of Example 16.

  This is done in O B (d 8 τ) [26, Lem. 6]. by successive resultant computations. They are polynomials of size O(d 3 ), O(d 2 τ) [2, Prop.8.72]. For v = s, t, u, we compute the gcd of R v 0 (v), . . . , R v D (v) in O B (d 10 + d 9 τ) [24, Lem. 2] and then the gcd of the later with H(v) in O B (d 6 τ) [5, Lem. 4]. Let hv (v) the gcd-free part of H(v). It has bitsize O(d + τ)

  5 t 5 --159s 4 t 6 + 45s 3 t 7 + 27s 7 t + 13s 6 t 2 + 195s 5 t 3 + 295s 4 t 4 + 195s 3 t 5 + 13s 2 t 6 + + 27s t 7 + 11s 6 + 93s 5 t + 211s 4 t 2 + 375s 3 t 3 + 211s 2 t 4 + 93s t 5 + 11t 6 + 13s 4 --31s 3 t -169s 2 t 2 -31s t 3 + 13t 4 + 17s 2 + 31st + 17t 2 + 15) .

the denominators. Calling the predicate Support for all these planes, amounts to isolating the roots of the system H(s) = 0 ,

For the triangles with non-smooth vertices that involve an endpoint, we distinguish three cases for the system that we solve:

• If one vertex is an endpoint and the other two cusps, the system is of the form {H(s) = H(t) = L(s, t, a, λ) = 0}, where a ∈ bd(I),

• If two vertices are endpoints and the third one is a cusp, the system is of the form {H(s) = L(s, a, b, λ) = 0}, where a, b ∈ bd(I),

• If all the vertices are endpoints, then we just have to solve the univariate equation L(a, b, c, λ) = 0, where a, b, c ∈ bd(I).

So, for a surface patch that corresponds to an arc of the graph of G with endpoints (s 1 , t 1 ) and (s 2 , t 2 ), the neighboring facets from each side can be determined.

Complexity analysis. For the bit-complexity analysis of the algorithm we use C(M, Λ, N) (Def. 3) to express it. The proof is given in detail in the next subsection. The output of the algorithm is a doubly connected linked list describing the facets of conv(ϕ(I)), which are O(d 3 ).

Corollary 12. Using the bit-complexity results of [START_REF] Katsamaki | On isolating roots in a multiple field extension[END_REF] for C(d, d + τ, 3) and [START_REF] Daouda | Bounds for polynomials on algebraic numbers and application to curve topology[END_REF] for C(d, d 6 τ, 1), the bit-complexity of the previous theorem becomes O B (d 13 + d 12 τ).

Proof of Theorem 11

Correctness

The correctness of the algorithm is based on Lem. 10 and the fact that the Support predicate correctly detects the bisecant surface patches that are on the boundary. On connecting the bisecant surface patches with triangles, we refer to the selection criterion of the gift-wrapping algorithm for the set of points ϕ(I). Given a segment that is on the boundary of the convex hull (and also on the boundary of a surface patch), the next point with whom it connects, is a point q ∈ ϕ(I) such that the plane that contains the segment and passes from q is strictly supporting for the convex hull. The connection phase in Step 4 respects this criterion.


Cécile Gasser
email: cecile.gasser@inrae.fr

Christian Chervaux

Peggy Garault

Jean-Michel Faurie

Françoise Rul

Diversity of carbohydrate utilization and uptake regulation in Streptococcus thermophilus

• Is used in new fermented products (dairy matrices supplemented with sugar or in plant-based food), containing a variety of carbohydrates in mixes.

• A lactic acid bacterium widely used in dairy industry.

• A wide diversity of strains used in various products.

• Has evolved and adapted to the dairy environment through a very efficient use of lactose.

Streptococcus thermophilus

?

How are sugars consumed in S. thermophilus species? How is sugar metabolism regulated?

• S. thermophilus is able to use 4 carbohydrates for growth, with high variability depending on sugar and strains

Methods

• Genomes of 39 strains were compared by searching for genes potentially involved in carbon metabolism.

• Utilization of galactose, fructose, glucose, sucrose and lactose, in mixture or not, was established by simultaneous monitoring of growth/acidification of the medium (M17) and dosage of the carbohydrates (HPLC) during growth.

• Promoter activities were studied with transcriptional fusions, in lactose, sucrose & glucose at 50, 25, 10, 5 and 1 g/L.

The better comprehension of the carbon metabolism and regulations involved in will allow to better control and orient S. thermophilus physiology in dairy or plant matrices Results: in silico analysis, growth and sugar consumption

••

  lactose and sucrose: growth for all strains -high final biomass • galactose: no/low growth • fructose: growth for 3 Sugar consumption by strain LMD-9 in dairy-like mix (up) and in a plantlike mix (down) The only genetic diversity between strains is localized in the sucrose operon repressor scrR and the fructose PTS transporter fruA scrR : pseudogene for 3/39 strains fruA : pseudogene for 36/39 strains • S. thermophilus ferments 4 carbohydrates, with different efficiency for growth according to strains • In sugar mixes, lactose is preferentially consumed • Sucrose is always consumed, whatever the sugars present in its environment • Regulation by glucose : Conclusion -no modulation of galR/scrB promoter activity -high repression of lactose and sucrose promoter activity catabolic repression ?