@inproceedings{3850,
abstract = {Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance ε in Hausdorff distance, as the Minkowski sum of another polygonal shape with a disk of fixed radius? If it does, we also seek a preferably simple solution shape P;P’s offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give a decision algorithm for fixed radius in O(nlogn) time that handles any polygonal shape. For convex shapes, the complexity drops to O(n), which is also the time required to compute a solution shape P with at most one more vertex than a vertex-minimal one.},
author = {Berberich, Eric and Halperin, Dan and Kerber, Michael and Pogalnikova, Roza},
location = {Dortmund, Germany},
pages = {12 -- 23},
publisher = {TU Dortmund},
title = {{Polygonal reconstruction from approximate offsets}},
year = {2010},
}
@inproceedings{3853,
abstract = {Quantitative languages are an extension of boolean languages that assign to each word a real number. Mean-payoff automata are finite automata with numerical weights on transitions that assign to each infinite path the long-run average of the transition weights. When the mode of branching of the automaton is deterministic, nondeterministic, or alternating, the corresponding class of quantitative languages is not robust as it is not closed under the pointwise operations of max, min, sum, and numerical complement. Nondeterministic and alternating mean-payoff automata are not decidable either, as the quantitative generalization of the problems of universality and language inclusion is undecidable. We introduce a new class of quantitative languages, defined by mean-payoff automaton expressions, which is robust and decidable: it is closed under the four pointwise operations, and we show that all decision problems are decidable for this class. Mean-payoff automaton expressions subsume deterministic meanpayoff automata, and we show that they have expressive power incomparable to nondeterministic and alternating mean-payoff automata. We also present for the first time an algorithm to compute distance between two quantitative languages, and in our case the quantitative languages are given as mean-payoff automaton expressions.},
author = {Chatterjee, Krishnendu and Doyen, Laurent and Edelsbrunner, Herbert and Henzinger, Thomas A and Rannou, Philippe},
location = {Paris, France},
pages = {269 -- 283},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Mean-payoff automaton expressions}},
doi = {10.1007/978-3-642-15375-4_19},
volume = {6269},
year = {2010},
}
@article{3901,
abstract = {We are interested in 3-dimensional images given as arrays of voxels with intensity values. Extending these values to acontinuous function, we study the robustness of homology classes in its level and interlevel sets, that is, the amount of perturbationneeded to destroy these classes. The structure of the homology classes and their robustness, over all level and interlevel sets, can bevisualized by a triangular diagram of dots obtained by computing the extended persistence of the function. We give a fast hierarchicalalgorithm using the dual complexes of oct-tree approximations of the function. In addition, we show that for balanced oct-trees, thedual complexes are geometrically realized in $R^3$ and can thus be used to construct level and interlevel sets. We apply these tools tostudy 3-dimensional images of plant root systems.},
author = {Bendich, Paul and Edelsbrunner, Herbert and Kerber, Michael},
journal = {IEEE Transactions of Visualization and Computer Graphics},
number = {6},
pages = {1251 -- 1260},
publisher = {IEEE},
title = {{Computing robustness and persistence for images}},
doi = {10.1109/TVCG.2010.139},
volume = {16},
year = {2010},
}
@inproceedings{3968,
abstract = {We describe an algorithm for segmenting three-dimensional medical imaging data modeled as a continuous function on a 3-manifold. It is related to watershed algorithms developed in image processing but is closer to its mathematical roots, which are Morse theory and homological algebra. It allows for the implicit treatment of an underlying mesh, thus combining the structural integrity of its mathematical foundations with the computational efficiency of image processing.},
author = {Edelsbrunner, Herbert and Harer, John},
location = {Zermatt, Switzerland},
pages = {36 -- 50},
publisher = {Springer},
title = {{The persistent Morse complex segmentation of a 3-manifold}},
doi = {10.1007/978-3-642-10470-1_4},
volume = {5903},
year = {2009},
}