Non-local length estimators and concave functions

Webpage : https://doi.org/10.1016/j.tcs.2017.06.005

In a previous work [2-MB17], the authors introduced the Non-Local Estimators (NLE), a wide class of polygonal length estimators including the sparse estimators and a part of the DSS ones. NLE are studied here under concavity assumption and it is shown that concavity almost doubles the multigrid converge rate w.r.t. the general case. Moreover, an example is given that proves that the obtained convergence rate is optimal. Besides, the notion of biconcavity relative to a NLE is proposed to describe the case where the digital polygon is also concave. Thanks to a counterexample, it is shown that concavity does not imply biconcavity. Then, an improved error bound is computed under the biconcavity assumption.

L. Mazo , E. Baudrier

Theoretical Computer Science , Volume 690 , page 73-90 - 2017

@Article{2-MB17,
 author = {Mazo, L. and Baudrier, E.},
 title = {Non-local length estimators and concave functions},
 journal = {Theoretical Computer Science},
 volume = {690},
 pages = {73-90},
 year = {2017},
 keywords = {discrete geometry; length estimation; multigrid convergence; concavity},
 doi = {10.1016/j.tcs.2017.06.005},
 x-international-audience = {Yes},
 x-language = {EN},
 url = {http://publis.icube.unistra.fr/2-MB17}
}