## 3 Reconstruction Algorithms
### Algorithm  
The main algorithm is organized as follows, starting from \(I^{(0)}\geq 2\) points and a dataset that is assumed to be consistent at the initial step \(n=0\). It goes through \(N\) iterations, where \(N\) is either fixed a priori, or obtained a posteriori once a stopping criterion is met. Note that \(q_{\text{new}}\) stands for the quality of a newly generated observation \(y_{\text{new}}\) for any new point \(x_{\text{new}}\) introduced by the algorithm. The latter is driven by the user-defined \"exchange rate\" \(\mathcal{E}\) as explained just above. At each step \(n\), the algorithm computes the weighted area \(\text{WA}^{(n)}\) as the minimum of the quality times the sum of the areas of the data points:  
\[\text{WA}^{(n)}=q_{-}^{(n)}\times\text{A}^{(n)}\,, \tag{5}\]  
where  
\[q_{-}^{(n)}=\min_{1\leq i\leq I^{(n)}}\{q_{i}^{(n)}\}\,,\quad\text{A}^{(n)}= \sum_{i=1}^{I^{(n)}-1}a_{i}^{(n)}\,, \tag{6}\]  
\(a_{i}^{(n)}\) is the area computed by Equation (3) at step \(n\) (see also Equation (9)), and \(I^{(n)}\) is the number of data points. Then it is divided into two parts according to the value of \(\text{WA}^{(n)}\) compared to \(\mathcal{E}\). Figure 1: Possible ground truth functions between two consecutive points \(x_{1}\) and \(x_{2}\), and our choice of piecewise constant interpolant. ```
Input:\(I^{(0)}\geq 2\), \(\{x^{(n)}_{i},y^{(0)}_{i},q^{(0)}_{i}\}_{i=1}^{I^{(0)}}\) and \(\mathcal{E}\). Output:\(\{x^{(N)}_{i},y^{(N)}_{i},q^{(N)}_{i}\}_{i=1}^{I^{(N)}}\) with \(I^{(N)}\geq I^{(0)}\). Initialization:  Get the worst quality point and its index: \(\bullet\quad q^{(0)}_{-}=\min\limits_{1\leq i\leq I^{(0)}}\{q^{(0)}_{i}\}\); \(\bullet\quad i^{(0)}_{-}=\operatorname*{arg\,min}\limits_{1\leq i\leq I^{(0)} }\{q^{(0)}_{i}\}\). Compute the area of each pair of data points: \(a^{(0)}_{i}=(x^{(0)}_{i+1}-x^{(0)}_{i})\times(y^{(0)}_{i+1}-y^{(0)}_{i})\). Get the biggest rectangle and its index: \(\bullet\quad a^{(0)}_{+}=\max\limits_{1\leq i\leq I^{(0)}-1}\{a^{(0)}_{i}\}\); \(\bullet\quad i^{(0)}_{+}=\operatorname*{arg\,max}\limits_{1\leq i\leq I^{(0) }-1}\{a^{(0)}_{i}\}\). Define the weighted area at step \(n=0\) as \(\operatorname{WA}^{(0)}=q^{(0)}_{-}\times\sum\limits_{i=1}^{I^{(0)}-1}a^{(0)}_ {i}\). while\(n\leq N\)do if\(\operatorname{WA}^{(n)}<\mathcal{E}\)then  Data points are unchanged: \(I^{(n+1)}=I^{(n)}\) and \(\{x^{(n+1)}_{i}\}_{i=1}^{I^{(n+1)}}=\{x^{(n)}_{i}\}_{i=1}^{I^{(n)}}\);  Store the old value \(y_{\text{old}}=y^{(n)}_{i^{(n)}_{-}}\); while\(y_{\text{new}}\leq y_{\text{old}}\)do  Compute a new value \(y_{\text{new}}=G(x^{(n)}_{i^{(n)}_{-}},q_{\text{new}})\);  end while  end while  Introduce a new point at the middle of the biggest rectangle: \(I^{(n+1)}=I^{(n)}+1\), \(x_{\text{new}}=\frac{1}{2}(x^{(n)}_{i^{(n)}_{+}}+x^{(n)}_{i^{(n)}_{+}+1})\), and \((x^{(n+1)}_{1},\dots,x^{(n+1)}_{i^{(n)}_{+}},x^{(n+1)}_{i^{(n)}_{+}+1},x^{(n+1 )}_{i^{(n)}_{+}+2},\dots,x^{(n+1)}_{I^{(n)}_{(n+1)}})=(x^{(n)}_{1},\dots,x^{(n) }_{i^{(n)}_{+}},x_{\text{new}},x^{(n)}_{i^{(n)}_{+}+1},\dots,x^{(n)}_{I^{(n)} _{(n)}})\);  Compute the new value \(y_{\text{new}}=G(x_{\text{new}},q_{\text{new}})\);  end while  Verify consistency of the pointwise observations \(\{y^{(n+1)}_{i}\}_{i=1}^{I^{(n+1)}}\) by checking their quality. If there are not consistent, recompute them until obtaining consistency and then update the quality vector;  Compute the new quality vector \(\{q^{(n+1)}_{i}\}_{i=1}^{I^{(n+1)}_{i=1}}\) and area vector \(\{a^{(n+1)}_{i}\}_{i=1}^{I^{(n+1)}}\);  Update \(q^{(n+1)}_{-},i^{(n+1)}_{-},a^{(n+1)}_{+}\) and \(\hat{a}^{(n+1)}_{+}\);  Compute \(\operatorname{WA}^{(n+1)}=q^{(n+1)}_{-}\times\sum\limits_{i=1}^{I^{(n+1)}-1}a^ {(n+1)}_{i}\); \(n=n+1\);  end while
```  
**Algorithm 1**Adaptive algorithm to reconstruct a monotonically increasing function \(F^{\ddagger}\)  
``` Input:\(I^{(0)}\geq 2\), \(\{x^{(0)}_{i},y^{(0)}_{i},q^{(0)}_{i}\}_{i=1}^{I^{(0)}}\) and \(\mathcal{E}\). Output:\(\{x^{(N)}_{i},y^{(N)}_{i},q^{(N)}_{i}\}_{i=1}^{I^{(N)}}\) with \(I^{(N)}\geq I^{(0)}\).