---
_id: '3330'
abstract:
- lang: eng
text: We consider the problem of approximating all real roots of a square-free polynomial
f. Given isolating intervals, our algorithm refines each of them to a width at
most 2-L, that is, each of the roots is approximated to L bits after the binary
point. Our method provides a certified answer for arbitrary real polynomials,
only requiring finite approximations of the polynomial coefficient and choosing
a suitable working precision adaptively. In this way, we get a correct algorithm
that is simple to implement and practically efficient. Our algorithm uses the
quadratic interval refinement method; we adapt that method to be able to cope
with inaccuracies when evaluating f, without sacrificing its quadratic convergence
behavior. We prove a bound on the bit complexity of our algorithm in terms of
degree, coefficient size and discriminant. Our bound improves previous work on
integer polynomials by a factor of deg f and essentially matches best known theoretical
bounds on root approximation which are obtained by very sophisticated algorithms.
article_processing_charge: No
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Sagraloff, Michael
last_name: Sagraloff
citation:
ama: 'Kerber M, Sagraloff M. Root refinement for real polynomials. In: Springer;
2011:209-216. doi:10.1145/1993886.1993920'
apa: 'Kerber, M., & Sagraloff, M. (2011). Root refinement for real polynomials
(pp. 209–216). Presented at the ISSAC: International Symposium on Symbolic and
Algebraic Computation, California, USA: Springer. https://doi.org/10.1145/1993886.1993920'
chicago: Kerber, Michael, and Michael Sagraloff. “Root Refinement for Real Polynomials,”
209–16. Springer, 2011. https://doi.org/10.1145/1993886.1993920.
ieee: 'M. Kerber and M. Sagraloff, “Root refinement for real polynomials,” presented
at the ISSAC: International Symposium on Symbolic and Algebraic Computation, California,
USA, 2011, pp. 209–216.'
ista: 'Kerber M, Sagraloff M. 2011. Root refinement for real polynomials. ISSAC:
International Symposium on Symbolic and Algebraic Computation, 209–216.'
mla: Kerber, Michael, and Michael Sagraloff. Root Refinement for Real Polynomials.
Springer, 2011, pp. 209–16, doi:10.1145/1993886.1993920.
short: M. Kerber, M. Sagraloff, in:, Springer, 2011, pp. 209–216.
conference:
end_date: 2011-06-11
location: California, USA
name: 'ISSAC: International Symposium on Symbolic and Algebraic Computation'
start_date: 2011-06-08
date_created: 2018-12-11T12:02:43Z
date_published: 2011-06-08T00:00:00Z
date_updated: 2021-01-12T07:42:42Z
day: '08'
department:
- _id: HeEd
doi: 10.1145/1993886.1993920
external_id:
arxiv:
- '1104.1362'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.1362
month: '06'
oa: 1
oa_version: Preprint
page: 209 - 216
publication_status: published
publisher: Springer
publist_id: '3304'
quality_controlled: '1'
scopus_import: 1
status: public
title: Root refinement for real polynomials
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3328'
abstract:
- lang: eng
text: 'We report on a generic uni- and bivariate algebraic kernel that is publicly
available with CGAL 3.7. It comprises complete, correct, though efficient state-of-the-art
implementations on polynomials, roots of polynomial systems, and the support to
analyze algebraic curves defined by bivariate polynomials. The kernel design is
generic, that is, various number types and substeps can be exchanged. It is accompanied
with a ready-to-use interface to enable arrangements induced by algebraic curves,
that have already been used as basis for various geometric applications, as arrangements
on Dupin cyclides or the triangulation of algebraic surfaces. We present two novel
applications: arrangements of rotated algebraic curves and Boolean set operations
on polygons bounded by segments of algebraic curves. We also provide experiments
showing that our general implementation is competitive and even often clearly
outperforms existing implementations that are explicitly tailored for specific
types of non-linear curves that are available in CGAL.'
article_processing_charge: No
author:
- first_name: Eric
full_name: Berberich, Eric
last_name: Berberich
- first_name: Michael
full_name: Hemmer, Michael
last_name: Hemmer
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Berberich E, Hemmer M, Kerber M. A generic algebraic kernel for non linear
geometric applications. In: ACM; 2011:179-186. doi:10.1145/1998196.1998224'
apa: 'Berberich, E., Hemmer, M., & Kerber, M. (2011). A generic algebraic kernel
for non linear geometric applications (pp. 179–186). Presented at the SCG: Symposium
on Computational Geometry, Paris, France: ACM. https://doi.org/10.1145/1998196.1998224'
chicago: Berberich, Eric, Michael Hemmer, and Michael Kerber. “A Generic Algebraic
Kernel for Non Linear Geometric Applications,” 179–86. ACM, 2011. https://doi.org/10.1145/1998196.1998224.
ieee: 'E. Berberich, M. Hemmer, and M. Kerber, “A generic algebraic kernel for non
linear geometric applications,” presented at the SCG: Symposium on Computational
Geometry, Paris, France, 2011, pp. 179–186.'
ista: 'Berberich E, Hemmer M, Kerber M. 2011. A generic algebraic kernel for non
linear geometric applications. SCG: Symposium on Computational Geometry, 179–186.'
mla: Berberich, Eric, et al. A Generic Algebraic Kernel for Non Linear Geometric
Applications. ACM, 2011, pp. 179–86, doi:10.1145/1998196.1998224.
short: E. Berberich, M. Hemmer, M. Kerber, in:, ACM, 2011, pp. 179–186.
conference:
end_date: 2011-06-15
location: Paris, France
name: 'SCG: Symposium on Computational Geometry'
start_date: 2011-06-13
date_created: 2018-12-11T12:02:42Z
date_published: 2011-06-13T00:00:00Z
date_updated: 2021-01-12T07:42:41Z
day: '13'
department:
- _id: HeEd
doi: 10.1145/1998196.1998224
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://hal.inria.fr/inria-00480031/file/RR-7274.pdf
month: '06'
oa: 1
oa_version: Published Version
page: 179 - 186
publication_status: published
publisher: ACM
publist_id: '3307'
quality_controlled: '1'
scopus_import: 1
status: public
title: A generic algebraic kernel for non linear geometric applications
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3334'
article_type: letter_note
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: János
full_name: Pach, János
last_name: Pach
- first_name: Günter
full_name: Ziegler, Günter
last_name: Ziegler
citation:
ama: Edelsbrunner H, Pach J, Ziegler G. Letter from the new editors-in-chief. Discrete
& Computational Geometry. 2011;45(1):1-2. doi:10.1007/s00454-010-9313-9
apa: Edelsbrunner, H., Pach, J., & Ziegler, G. (2011). Letter from the new editors-in-chief.
Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-010-9313-9
chicago: Edelsbrunner, Herbert, János Pach, and Günter Ziegler. “Letter from the
New Editors-in-Chief.” Discrete & Computational Geometry. Springer,
2011. https://doi.org/10.1007/s00454-010-9313-9.
ieee: H. Edelsbrunner, J. Pach, and G. Ziegler, “Letter from the new editors-in-chief,”
Discrete & Computational Geometry, vol. 45, no. 1. Springer, pp. 1–2,
2011.
ista: Edelsbrunner H, Pach J, Ziegler G. 2011. Letter from the new editors-in-chief.
Discrete & Computational Geometry. 45(1), 1–2.
mla: Edelsbrunner, Herbert, et al. “Letter from the New Editors-in-Chief.” Discrete
& Computational Geometry, vol. 45, no. 1, Springer, 2011, pp. 1–2, doi:10.1007/s00454-010-9313-9.
short: H. Edelsbrunner, J. Pach, G. Ziegler, Discrete & Computational Geometry
45 (2011) 1–2.
date_created: 2018-12-11T12:02:44Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:44Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s00454-010-9313-9
intvolume: ' 45'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 1 - 2
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '3297'
quality_controlled: '1'
scopus_import: 1
status: public
title: Letter from the new editors-in-chief
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 45
year: '2011'
...
---
_id: '3367'
abstract:
- lang: eng
text: In this paper, we present the first output-sensitive algorithm to compute
the persistence diagram of a filtered simplicial complex. For any Γ>0, it returns
only those homology classes with persistence at least Γ. Instead of the classical
reduction via column operations, our algorithm performs rank computations on submatrices
of the boundary matrix. For an arbitrary constant δ ∈ (0,1), the running time
is O(C(1-δ)ΓR(n)log n), where C(1-δ)Γ is the number of homology classes with persistence
at least (1-δ)Γ, n is the total number of simplices, and R(n) is the complexity
of computing the rank of an n x n matrix with O(n) nonzero entries. Depending
on the choice of the rank algorithm, this yields a deterministic O(C(1-δ)Γn2.376)
algorithm, a O(C(1-δ)Γn2.28) Las-Vegas algorithm, or a O(C(1-δ)Γn2+ε) Monte-Carlo
algorithm for an arbitrary ε>0.
article_processing_charge: No
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Chen C, Kerber M. An output sensitive algorithm for persistent homology. In:
ACM; 2011:207-216. doi:10.1145/1998196.1998228'
apa: 'Chen, C., & Kerber, M. (2011). An output sensitive algorithm for persistent
homology (pp. 207–216). Presented at the SoCG: Symposium on Computational Geometry,
Paris, France: ACM. https://doi.org/10.1145/1998196.1998228'
chicago: Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent
Homology,” 207–16. ACM, 2011. https://doi.org/10.1145/1998196.1998228.
ieee: 'C. Chen and M. Kerber, “An output sensitive algorithm for persistent homology,”
presented at the SoCG: Symposium on Computational Geometry, Paris, France, 2011,
pp. 207–216.'
ista: 'Chen C, Kerber M. 2011. An output sensitive algorithm for persistent homology.
SoCG: Symposium on Computational Geometry, 207–216.'
mla: Chen, Chao, and Michael Kerber. An Output Sensitive Algorithm for Persistent
Homology. ACM, 2011, pp. 207–16, doi:10.1145/1998196.1998228.
short: C. Chen, M. Kerber, in:, ACM, 2011, pp. 207–216.
conference:
end_date: 2011-06-15
location: Paris, France
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2011-06-13
date_created: 2018-12-11T12:02:56Z
date_published: 2011-06-13T00:00:00Z
date_updated: 2023-02-23T11:05:04Z
day: '13'
department:
- _id: HeEd
doi: 10.1145/1998196.1998228
language:
- iso: eng
month: '06'
oa_version: None
page: 207 - 216
publication_status: published
publisher: ACM
publist_id: '3245'
quality_controlled: '1'
related_material:
record:
- id: '2939'
relation: later_version
status: public
scopus_import: 1
status: public
title: An output sensitive algorithm for persistent homology
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3781'
abstract:
- lang: eng
text: We bound the difference in length of two curves in terms of their total curvatures
and the Fréchet distance. The bound is independent of the dimension of the ambient
Euclidean space, it improves upon a bound by Cohen-Steiner and Edelsbrunner, and
it generalizes a result by Fáry and Chakerian.
acknowledgement: Funded by Graduate Aid in Areas of National Need (GAANN) Fellowship.
author:
- first_name: Brittany Terese
full_name: Fasy, Brittany Terese
id: F65D502E-E68D-11E9-9252-C644099818F6
last_name: Fasy
citation:
ama: Fasy BT. The difference in length of curves in R^n. Acta Sci Math (Szeged).
2011;77(1-2):359-367.
apa: Fasy, B. T. (2011). The difference in length of curves in R^n. Acta Sci.
Math. (Szeged). Szegedi Tudományegyetem.
chicago: Fasy, Brittany Terese. “The Difference in Length of Curves in R^n.” Acta
Sci. Math. (Szeged). Szegedi Tudományegyetem, 2011.
ieee: B. T. Fasy, “The difference in length of curves in R^n,” Acta Sci. Math.
(Szeged), vol. 77, no. 1–2. Szegedi Tudományegyetem, pp. 359–367, 2011.
ista: Fasy BT. 2011. The difference in length of curves in R^n. Acta Sci. Math.
(Szeged). 77(1–2), 359–367.
mla: Fasy, Brittany Terese. “The Difference in Length of Curves in R^n.” Acta
Sci. Math. (Szeged), vol. 77, no. 1–2, Szegedi Tudományegyetem, 2011, pp.
359–67.
short: B.T. Fasy, Acta Sci. Math. (Szeged) 77 (2011) 359–367.
date_created: 2018-12-11T12:05:08Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:52:09Z
day: '01'
department:
- _id: HeEd
intvolume: ' 77'
issue: 1-2
language:
- iso: eng
month: '01'
oa_version: None
page: 359 - 367
publication: Acta Sci. Math. (Szeged)
publication_status: published
publisher: Szegedi Tudományegyetem
publist_id: '2446'
quality_controlled: '1'
status: public
title: The difference in length of curves in R^n
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 77
year: '2011'
...
---
_id: '3796'
abstract:
- lang: eng
text: We address the problem of covering ℝ n with congruent balls, while minimizing
the number of balls that contain an average point. Considering the 1-parameter
family of lattices defined by stretching or compressing the integer grid in diagonal
direction, we give a closed formula for the covering density that depends on the
distortion parameter. We observe that our family contains the thinnest lattice
coverings in dimensions 2 to 5. We also consider the problem of packing congruent
balls in ℝ n , for which we give a closed formula for the packing density as well.
Again we observe that our family contains optimal configurations, this time densest
packings in dimensions 2 and 3.
alternative_title:
- LNCS
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Edelsbrunner H, Kerber M. Covering and packing with spheres by diagonal distortion
in R^n. In: Calude C, Rozenberg G, Salomaa A, eds. Rainbow of Computer Science.
Vol 6570. Dedicated to Hermann Maurer on the Occasion of His 70th Birthday. Springer;
2011:20-35. doi:10.1007/978-3-642-19391-0_2'
apa: Edelsbrunner, H., & Kerber, M. (2011). Covering and packing with spheres
by diagonal distortion in R^n. In C. Calude, G. Rozenberg, & A. Salomaa (Eds.),
Rainbow of Computer Science (Vol. 6570, pp. 20–35). Springer. https://doi.org/10.1007/978-3-642-19391-0_2
chicago: Edelsbrunner, Herbert, and Michael Kerber. “Covering and Packing with Spheres
by Diagonal Distortion in R^n.” In Rainbow of Computer Science, edited
by Cristian Calude, Grzegorz Rozenberg, and Arto Salomaa, 6570:20–35. Dedicated
to Hermann Maurer on the Occasion of His 70th Birthday. Springer, 2011. https://doi.org/10.1007/978-3-642-19391-0_2.
ieee: H. Edelsbrunner and M. Kerber, “Covering and packing with spheres by diagonal
distortion in R^n,” in Rainbow of Computer Science, vol. 6570, C. Calude,
G. Rozenberg, and A. Salomaa, Eds. Springer, 2011, pp. 20–35.
ista: 'Edelsbrunner H, Kerber M. 2011.Covering and packing with spheres by diagonal
distortion in R^n. In: Rainbow of Computer Science. LNCS, vol. 6570, 20–35.'
mla: Edelsbrunner, Herbert, and Michael Kerber. “Covering and Packing with Spheres
by Diagonal Distortion in R^n.” Rainbow of Computer Science, edited by
Cristian Calude et al., vol. 6570, Springer, 2011, pp. 20–35, doi:10.1007/978-3-642-19391-0_2.
short: H. Edelsbrunner, M. Kerber, in:, C. Calude, G. Rozenberg, A. Salomaa (Eds.),
Rainbow of Computer Science, Springer, 2011, pp. 20–35.
date_created: 2018-12-11T12:05:13Z
date_published: 2011-05-03T00:00:00Z
date_updated: 2021-01-12T07:52:15Z
day: '03'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/978-3-642-19391-0_2
editor:
- first_name: Cristian
full_name: Calude, Cristian
last_name: Calude
- first_name: Grzegorz
full_name: Rozenberg, Grzegorz
last_name: Rozenberg
- first_name: Arto
full_name: Salomaa, Arto
last_name: Salomaa
file:
- access_level: open_access
checksum: aaf22b4d7bd4277ffe8db532119cf474
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:42Z
date_updated: 2020-07-14T12:46:16Z
file_id: '4640'
file_name: IST-2016-539-v1+1_2011-B-01-CoveringPacking.pdf
file_size: 436875
relation: main_file
file_date_updated: 2020-07-14T12:46:16Z
has_accepted_license: '1'
intvolume: ' 6570'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Submitted Version
page: 20 - 35
publication: Rainbow of Computer Science
publication_status: published
publisher: Springer
publist_id: '2427'
pubrep_id: '539'
quality_controlled: '1'
series_title: Dedicated to Hermann Maurer on the Occasion of His 70th Birthday
status: public
title: Covering and packing with spheres by diagonal distortion in R^n
type: book_chapter
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6570
year: '2011'
...
---
_id: '3965'
abstract:
- lang: eng
text: The elevation function on a smoothly embedded 2-manifold in R-3 reflects the
multiscale topography of cavities and protrusions as local maxima. The function
has been useful in identifying coarse docking configurations for protein pairs.
Transporting the concept from the smooth to the piecewise linear category, this
paper describes an algorithm for finding all local maxima. While its worst-case
running time is the same as of the algorithm used in prior work, its performance
in practice is orders of magnitudes superior. We cast light on this improvement
by relating the running time to the total absolute Gaussian curvature of the 2-manifold.
author:
- first_name: Bei
full_name: Wang, Bei
last_name: Wang
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Dmitriy
full_name: Morozov, Dmitriy
last_name: Morozov
citation:
ama: Wang B, Edelsbrunner H, Morozov D. Computing elevation maxima by searching
the Gauss sphere. Journal of Experimental Algorithmics. 2011;16(2.2):1-13.
doi:10.1145/1963190.1970375
apa: Wang, B., Edelsbrunner, H., & Morozov, D. (2011). Computing elevation maxima
by searching the Gauss sphere. Journal of Experimental Algorithmics. ACM.
https://doi.org/10.1145/1963190.1970375
chicago: Wang, Bei, Herbert Edelsbrunner, and Dmitriy Morozov. “Computing Elevation
Maxima by Searching the Gauss Sphere.” Journal of Experimental Algorithmics.
ACM, 2011. https://doi.org/10.1145/1963190.1970375.
ieee: B. Wang, H. Edelsbrunner, and D. Morozov, “Computing elevation maxima by searching
the Gauss sphere,” Journal of Experimental Algorithmics, vol. 16, no. 2.2.
ACM, pp. 1–13, 2011.
ista: Wang B, Edelsbrunner H, Morozov D. 2011. Computing elevation maxima by searching
the Gauss sphere. Journal of Experimental Algorithmics. 16(2.2), 1–13.
mla: Wang, Bei, et al. “Computing Elevation Maxima by Searching the Gauss Sphere.”
Journal of Experimental Algorithmics, vol. 16, no. 2.2, ACM, 2011, pp.
1–13, doi:10.1145/1963190.1970375.
short: B. Wang, H. Edelsbrunner, D. Morozov, Journal of Experimental Algorithmics
16 (2011) 1–13.
date_created: 2018-12-11T12:06:09Z
date_published: 2011-05-01T00:00:00Z
date_updated: 2021-01-12T07:53:31Z
day: '01'
department:
- _id: HeEd
doi: 10.1145/1963190.1970375
intvolume: ' 16'
issue: '2.2'
language:
- iso: eng
month: '05'
oa_version: None
page: 1 - 13
publication: Journal of Experimental Algorithmics
publication_status: published
publisher: ACM
publist_id: '2161'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computing elevation maxima by searching the Gauss sphere
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2011'
...
---
_id: '3271'
abstract:
- lang: eng
text: In this paper we present an efficient framework for computation of persis-
tent homology of cubical data in arbitrary dimensions. An existing algorithm using
simplicial complexes is adapted to the setting of cubical complexes. The proposed
approach enables efficient application of persistent homology in domains where
the data is naturally given in a cubical form. By avoiding triangulation of the
data, we significantly reduce the size of the complex. We also present a data-structure
de- signed to compactly store and quickly manipulate cubical complexes. By means
of numerical experiments, we show high speed and memory efficiency of our ap-
proach. We compare our framework to other available implementations, showing its
superiority. Finally, we report performance on selected 3D and 4D data-sets.
alternative_title:
- Theory, Algorithms, and Applications
author:
- first_name: Hubert
full_name: Wagner, Hubert
last_name: Wagner
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Erald
full_name: Vuçini, Erald
last_name: Vuçini
citation:
ama: 'Wagner H, Chen C, Vuçini E. Efficient computation of persistent homology for
cubical data. In: Peikert R, Hauser H, Carr H, Fuchs R, eds. Topological Methods
in Data Analysis and Visualization II. Springer; 2011:91-106. doi:10.1007/978-3-642-23175-9_7'
apa: Wagner, H., Chen, C., & Vuçini, E. (2011). Efficient computation of persistent
homology for cubical data. In R. Peikert, H. Hauser, H. Carr, & R. Fuchs (Eds.),
Topological Methods in Data Analysis and Visualization II (pp. 91–106).
Springer. https://doi.org/10.1007/978-3-642-23175-9_7
chicago: Wagner, Hubert, Chao Chen, and Erald Vuçini. “Efficient Computation of
Persistent Homology for Cubical Data.” In Topological Methods in Data Analysis
and Visualization II, edited by Ronald Peikert, Helwig Hauser, Hamish Carr,
and Raphael Fuchs, 91–106. Springer, 2011. https://doi.org/10.1007/978-3-642-23175-9_7.
ieee: H. Wagner, C. Chen, and E. Vuçini, “Efficient computation of persistent homology
for cubical data,” in Topological Methods in Data Analysis and Visualization
II, R. Peikert, H. Hauser, H. Carr, and R. Fuchs, Eds. Springer, 2011, pp.
91–106.
ista: 'Wagner H, Chen C, Vuçini E. 2011.Efficient computation of persistent homology
for cubical data. In: Topological Methods in Data Analysis and Visualization II.
Theory, Algorithms, and Applications, , 91–106.'
mla: Wagner, Hubert, et al. “Efficient Computation of Persistent Homology for Cubical
Data.” Topological Methods in Data Analysis and Visualization II, edited
by Ronald Peikert et al., Springer, 2011, pp. 91–106, doi:10.1007/978-3-642-23175-9_7.
short: H. Wagner, C. Chen, E. Vuçini, in:, R. Peikert, H. Hauser, H. Carr, R. Fuchs
(Eds.), Topological Methods in Data Analysis and Visualization II, Springer, 2011,
pp. 91–106.
date_created: 2018-12-11T12:02:23Z
date_published: 2011-11-14T00:00:00Z
date_updated: 2021-01-12T07:42:18Z
day: '14'
department:
- _id: HeEd
doi: 10.1007/978-3-642-23175-9_7
editor:
- first_name: Ronald
full_name: Peikert, Ronald
last_name: Peikert
- first_name: Helwig
full_name: Hauser, Helwig
last_name: Hauser
- first_name: Hamish
full_name: Carr, Hamish
last_name: Carr
- first_name: Raphael
full_name: Fuchs, Raphael
last_name: Fuchs
language:
- iso: eng
month: '11'
oa_version: None
page: 91 - 106
publication: Topological Methods in Data Analysis and Visualization II
publication_status: published
publisher: Springer
publist_id: '3375'
quality_controlled: '1'
scopus_import: 1
status: public
title: Efficient computation of persistent homology for cubical data
type: book_chapter
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3270'
abstract:
- lang: eng
text: 'The persistence diagram of a filtered simplicial com- plex is usually computed
by reducing the boundary matrix of the complex. We introduce a simple op- timization
technique: by processing the simplices of the complex in decreasing dimension,
we can “kill” columns (i.e., set them to zero) without reducing them. This technique
completely avoids reduction on roughly half of the columns. We demonstrate that
this idea significantly improves the running time of the reduction algorithm in
practice. We also give an output-sensitive complexity analysis for the new al-
gorithm which yields to sub-cubic asymptotic bounds under certain assumptions.'
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Chen C, Kerber M. Persistent homology computation with a twist. In: TU Dortmund;
2011:197-200.'
apa: 'Chen, C., & Kerber, M. (2011). Persistent homology computation with a
twist (pp. 197–200). Presented at the EuroCG: European Workshop on Computational
Geometry, Morschach, Switzerland: TU Dortmund.'
chicago: Chen, Chao, and Michael Kerber. “Persistent Homology Computation with a
Twist,” 197–200. TU Dortmund, 2011.
ieee: 'C. Chen and M. Kerber, “Persistent homology computation with a twist,” presented
at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland,
2011, pp. 197–200.'
ista: 'Chen C, Kerber M. 2011. Persistent homology computation with a twist. EuroCG:
European Workshop on Computational Geometry, 197–200.'
mla: Chen, Chao, and Michael Kerber. Persistent Homology Computation with a Twist.
TU Dortmund, 2011, pp. 197–200.
short: C. Chen, M. Kerber, in:, TU Dortmund, 2011, pp. 197–200.
conference:
end_date: 2011-03-30
location: Morschach, Switzerland
name: 'EuroCG: European Workshop on Computational Geometry'
start_date: 2011-03-28
date_created: 2018-12-11T12:02:22Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:17Z
day: '01'
department:
- _id: HeEd
language:
- iso: eng
month: '01'
oa_version: None
page: 197 - 200
publication_status: published
publisher: TU Dortmund
publist_id: '3376'
quality_controlled: '1'
status: public
title: Persistent homology computation with a twist
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3312'
abstract:
- lang: eng
text: We study the 3D reconstruction of plant roots from multiple 2D images. To
meet the challenge caused by the delicate nature of thin branches, we make three
innovations to cope with the sensitivity to image quality and calibration. First,
we model the background as a harmonic function to improve the segmentation of
the root in each 2D image. Second, we develop the concept of the regularized visual
hull which reduces the effect of jittering and refraction by ensuring consistency
with one 2D image. Third, we guarantee connectedness through adjustments to the
3D reconstruction that minimize global error. Our software is part of a biological
phenotype/genotype study of agricultural root systems. It has been tested on more
than 40 plant roots and results are promising in terms of reconstruction quality
and efficiency.
acknowledgement: This research is supported by the National Science Foundation (NSF)
under grant DBI-0820624.
article_number: '6126475'
article_processing_charge: No
author:
- first_name: Ying
full_name: Zheng, Ying
last_name: Zheng
- first_name: Steve
full_name: Gu, Steve
last_name: Gu
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Carlo
full_name: Tomasi, Carlo
last_name: Tomasi
- first_name: Philip
full_name: Benfey, Philip
last_name: Benfey
citation:
ama: Zheng Y, Gu S, Edelsbrunner H, Tomasi C, Benfey P. Detailed Reconstruction
of 3D Plant Root Shape. IEEE; 2011. doi:10.1109/ICCV.2011.6126475
apa: 'Zheng, Y., Gu, S., Edelsbrunner, H., Tomasi, C., & Benfey, P. (2011).
Detailed reconstruction of 3D plant root shape. Proceedings of the IEEE
International Conference on Computer Vision. Barcelona, Spain: IEEE. https://doi.org/10.1109/ICCV.2011.6126475'
chicago: Zheng, Ying, Steve Gu, Herbert Edelsbrunner, Carlo Tomasi, and Philip Benfey.
Detailed Reconstruction of 3D Plant Root Shape. Proceedings of the IEEE
International Conference on Computer Vision. IEEE, 2011. https://doi.org/10.1109/ICCV.2011.6126475.
ieee: Y. Zheng, S. Gu, H. Edelsbrunner, C. Tomasi, and P. Benfey, Detailed reconstruction
of 3D plant root shape. IEEE, 2011.
ista: Zheng Y, Gu S, Edelsbrunner H, Tomasi C, Benfey P. 2011. Detailed reconstruction
of 3D plant root shape, IEEE,p.
mla: Zheng, Ying, et al. “Detailed Reconstruction of 3D Plant Root Shape.” Proceedings
of the IEEE International Conference on Computer Vision, 6126475, IEEE, 2011,
doi:10.1109/ICCV.2011.6126475.
short: Y. Zheng, S. Gu, H. Edelsbrunner, C. Tomasi, P. Benfey, Detailed Reconstruction
of 3D Plant Root Shape, IEEE, 2011.
conference:
end_date: 2011-11-13
location: Barcelona, Spain
name: 'ICCV: International Conference on Computer Vision'
start_date: 2011-11-06
date_created: 2018-12-11T12:02:36Z
date_published: 2011-12-31T00:00:00Z
date_updated: 2020-07-14T23:03:43Z
day: '31'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1109/ICCV.2011.6126475
file:
- access_level: open_access
checksum: 30a33564b7b45a7ee31610898267fd0e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:04Z
date_updated: 2020-07-14T12:46:07Z
file_id: '4727'
file_name: IST-2016-541-v1+1_2011-P-07-RootReconstruction.pdf
file_size: 5622728
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
publication: Proceedings of the IEEE International Conference on Computer Vision
publication_status: published
publisher: IEEE
publist_id: '3328'
pubrep_id: '541'
quality_controlled: '1'
status: public
title: Detailed reconstruction of 3D plant root shape
type: conference_poster
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3313'
abstract:
- lang: eng
text: Interpreting an image as a function on a compact sub- set of the Euclidean
plane, we get its scale-space by diffu- sion, spreading the image over the entire
plane. This gener- ates a 1-parameter family of functions alternatively defined
as convolutions with a progressively wider Gaussian ker- nel. We prove that the
corresponding 1-parameter family of persistence diagrams have norms that go rapidly
to zero as time goes to infinity. This result rationalizes experimental observations
about scale-space. We hope this will lead to targeted improvements of related
computer vision methods.
article_number: '6126271'
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Chen C, Edelsbrunner H. Diffusion runs low on persistence fast. In: Proceedings
of the IEEE International Conference on Computer Vision. IEEE; 2011. doi:10.1109/ICCV.2011.6126271'
apa: 'Chen, C., & Edelsbrunner, H. (2011). Diffusion runs low on persistence
fast. In Proceedings of the IEEE International Conference on Computer Vision.
Barcelona, Spain: IEEE. https://doi.org/10.1109/ICCV.2011.6126271'
chicago: Chen, Chao, and Herbert Edelsbrunner. “Diffusion Runs Low on Persistence
Fast.” In Proceedings of the IEEE International Conference on Computer Vision.
IEEE, 2011. https://doi.org/10.1109/ICCV.2011.6126271.
ieee: C. Chen and H. Edelsbrunner, “Diffusion runs low on persistence fast,” in
Proceedings of the IEEE International Conference on Computer Vision, Barcelona,
Spain, 2011.
ista: 'Chen C, Edelsbrunner H. 2011. Diffusion runs low on persistence fast. Proceedings
of the IEEE International Conference on Computer Vision. ICCV: International Conference
on Computer Vision, 6126271.'
mla: Chen, Chao, and Herbert Edelsbrunner. “Diffusion Runs Low on Persistence Fast.”
Proceedings of the IEEE International Conference on Computer Vision, 6126271,
IEEE, 2011, doi:10.1109/ICCV.2011.6126271.
short: C. Chen, H. Edelsbrunner, in:, Proceedings of the IEEE International Conference
on Computer Vision, IEEE, 2011.
conference:
end_date: 2011-11-13
location: Barcelona, Spain
name: 'ICCV: International Conference on Computer Vision'
start_date: 2011-11-06
date_created: 2018-12-11T12:02:37Z
date_published: 2011-11-06T00:00:00Z
date_updated: 2021-01-12T07:42:35Z
day: '06'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1109/ICCV.2011.6126271
file:
- access_level: open_access
checksum: 6984684081ba123808b344f9f2e64a8f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:28Z
date_updated: 2020-07-14T12:46:07Z
file_id: '5282'
file_name: IST-2016-540-v1+1_2011-P-08-RunEmpty.pdf
file_size: 614050
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Submitted Version
publication: Proceedings of the IEEE International Conference on Computer Vision
publication_status: published
publisher: IEEE
publist_id: '3327'
pubrep_id: '540'
quality_controlled: '1'
scopus_import: 1
status: public
title: Diffusion runs low on persistence fast
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3311'
abstract:
- lang: eng
text: Alpha shapes have been conceived in 1981 as an attempt to define the shape
of a finite set of point in the plane. Since then, connections to diverse areas
in the sciences and engineering have developed, including to pattern recognition,
digital shape sampling and processing, and structural molecular biology. This
survey begins with a historical account and discusses geometric, algorithmic,
topological, and combinatorial aspects of alpha shapes in this sequence.
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Edelsbrunner H. Alpha shapes - a survey. In: van de Weygaert R, Vegter G,
Ritzerveld J, Icke V, eds. Tessellations in the Sciences: Virtues, Techniques
and Applications of Geometric Tilings. Springer.'
apa: 'Edelsbrunner, H. (n.d.). Alpha shapes - a survey. In R. van de Weygaert, G.
Vegter, J. Ritzerveld, & V. Icke (Eds.), Tessellations in the Sciences:
Virtues, Techniques and Applications of Geometric Tilings. Springer.'
chicago: 'Edelsbrunner, Herbert. “Alpha Shapes - a Survey.” In Tessellations
in the Sciences: Virtues, Techniques and Applications of Geometric Tilings,
edited by R van de Weygaert, G Vegter, J Ritzerveld, and V Icke. Springer, n.d.'
ieee: 'H. Edelsbrunner, “Alpha shapes - a survey,” in Tessellations in the Sciences:
Virtues, Techniques and Applications of Geometric Tilings, R. van de Weygaert,
G. Vegter, J. Ritzerveld, and V. Icke, Eds. Springer.'
ista: 'Edelsbrunner H.Alpha shapes - a survey. In: Tessellations in the Sciences:
Virtues, Techniques and Applications of Geometric Tilings. .'
mla: 'Edelsbrunner, Herbert. “Alpha Shapes - a Survey.” Tessellations in the
Sciences: Virtues, Techniques and Applications of Geometric Tilings, edited
by R van de Weygaert et al., Springer.'
short: 'H. Edelsbrunner, in:, R. van de Weygaert, G. Vegter, J. Ritzerveld, V. Icke
(Eds.), Tessellations in the Sciences: Virtues, Techniques and Applications of
Geometric Tilings, Springer, n.d.'
date_created: 2018-12-11T12:02:36Z
date_published: 2011-12-31T00:00:00Z
date_updated: 2022-05-24T07:56:30Z
day: '31'
ddc:
- '510'
department:
- _id: HeEd
editor:
- first_name: R
full_name: van de Weygaert, R
last_name: van de Weygaert
- first_name: G
full_name: Vegter, G
last_name: Vegter
- first_name: J
full_name: Ritzerveld, J
last_name: Ritzerveld
- first_name: V
full_name: Icke, V
last_name: Icke
file:
- access_level: open_access
checksum: a592ea438351e7280eea993a7713ab8f
content_type: application/pdf
creator: dernst
date_created: 2022-05-24T07:55:05Z
date_updated: 2022-05-24T07:55:05Z
file_id: '11408'
file_name: 2010_AlphaShapes.pdf
file_size: 475254
relation: main_file
success: 1
file_date_updated: 2022-05-24T07:55:05Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
publication: 'Tessellations in the Sciences: Virtues, Techniques and Applications
of Geometric Tilings'
publication_status: inpress
publisher: Springer
publist_id: '3329'
quality_controlled: '1'
status: public
title: Alpha shapes - a survey
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3377'
abstract:
- lang: eng
text: By definition, transverse intersections are stable under in- finitesimal perturbations.
Using persistent homology, we ex- tend this notion to sizeable perturbations.
Specifically, we assign to each homology class of the intersection its robust-
ness, the magnitude of a perturbation necessary to kill it, and prove that robustness
is stable. Among the applications of this result is a stable notion of robustness
for fixed points of continuous mappings and a statement of stability for con-
tours of smooth mappings.
acknowledgement: This research is partially supported by the Defense Advanced Research
Projects Agency (DARPA) under grants HR0011-05-1-0007 and HR0011-05-1-0057.
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Dmitriy
full_name: Morozov, Dmitriy
last_name: Morozov
- first_name: Amit
full_name: Patel, Amit
id: 34A254A0-F248-11E8-B48F-1D18A9856A87
last_name: Patel
citation:
ama: Edelsbrunner H, Morozov D, Patel A. Quantifying transversality by measuring
the robustness of intersections. Foundations of Computational Mathematics.
2011;11(3):345-361. doi:10.1007/s10208-011-9090-8
apa: Edelsbrunner, H., Morozov, D., & Patel, A. (2011). Quantifying transversality
by measuring the robustness of intersections. Foundations of Computational
Mathematics. Springer. https://doi.org/10.1007/s10208-011-9090-8
chicago: Edelsbrunner, Herbert, Dmitriy Morozov, and Amit Patel. “Quantifying Transversality
by Measuring the Robustness of Intersections.” Foundations of Computational
Mathematics. Springer, 2011. https://doi.org/10.1007/s10208-011-9090-8.
ieee: H. Edelsbrunner, D. Morozov, and A. Patel, “Quantifying transversality by
measuring the robustness of intersections,” Foundations of Computational Mathematics,
vol. 11, no. 3. Springer, pp. 345–361, 2011.
ista: Edelsbrunner H, Morozov D, Patel A. 2011. Quantifying transversality by measuring
the robustness of intersections. Foundations of Computational Mathematics. 11(3),
345–361.
mla: Edelsbrunner, Herbert, et al. “Quantifying Transversality by Measuring the
Robustness of Intersections.” Foundations of Computational Mathematics,
vol. 11, no. 3, Springer, 2011, pp. 345–61, doi:10.1007/s10208-011-9090-8.
short: H. Edelsbrunner, D. Morozov, A. Patel, Foundations of Computational Mathematics
11 (2011) 345–361.
date_created: 2018-12-11T12:02:59Z
date_published: 2011-06-01T00:00:00Z
date_updated: 2021-01-12T07:43:04Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s10208-011-9090-8
intvolume: ' 11'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/0911.2142
month: '06'
oa: 1
oa_version: Submitted Version
page: 345 - 361
publication: Foundations of Computational Mathematics
publication_status: published
publisher: Springer
publist_id: '3230'
quality_controlled: '1'
scopus_import: 1
status: public
title: Quantifying transversality by measuring the robustness of intersections
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2011'
...
---
_id: '3378'
abstract:
- lang: eng
text: The theory of intersection homology was developed to study the singularities
of a topologically stratified space. This paper in- corporates this theory into
the already developed framework of persistent homology. We demonstrate that persistent
intersec- tion homology gives useful information about the relationship between
an embedded stratified space and its singularities. We give, and prove the correctness
of, an algorithm for the computa- tion of the persistent intersection homology
groups of a filtered simplicial complex equipped with a stratification by subcom-
plexes. We also derive, from Poincare ́ Duality, some structural results about
persistent intersection homology.
acknowledgement: This research was partially supported by the Defense Advanced Research
Projects Agency (DARPA) under grant HR0011-05-1-0007.
author:
- first_name: Paul
full_name: Bendich, Paul
id: 43F6EC54-F248-11E8-B48F-1D18A9856A87
last_name: Bendich
- first_name: John
full_name: Harer, John
last_name: Harer
citation:
ama: Bendich P, Harer J. Persistent intersection homology. Foundations of Computational
Mathematics. 2011;11(3):305-336. doi:10.1007/s10208-010-9081-1
apa: Bendich, P., & Harer, J. (2011). Persistent intersection homology. Foundations
of Computational Mathematics. Springer. https://doi.org/10.1007/s10208-010-9081-1
chicago: Bendich, Paul, and John Harer. “Persistent Intersection Homology.” Foundations
of Computational Mathematics. Springer, 2011. https://doi.org/10.1007/s10208-010-9081-1.
ieee: P. Bendich and J. Harer, “Persistent intersection homology,” Foundations
of Computational Mathematics, vol. 11, no. 3. Springer, pp. 305–336, 2011.
ista: Bendich P, Harer J. 2011. Persistent intersection homology. Foundations of
Computational Mathematics. 11(3), 305–336.
mla: Bendich, Paul, and John Harer. “Persistent Intersection Homology.” Foundations
of Computational Mathematics, vol. 11, no. 3, Springer, 2011, pp. 305–36,
doi:10.1007/s10208-010-9081-1.
short: P. Bendich, J. Harer, Foundations of Computational Mathematics 11 (2011)
305–336.
date_created: 2018-12-11T12:02:59Z
date_published: 2011-06-01T00:00:00Z
date_updated: 2021-01-12T07:43:04Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s10208-010-9081-1
intvolume: ' 11'
issue: '3'
language:
- iso: eng
month: '06'
oa_version: None
page: 305 - 336
publication: Foundations of Computational Mathematics
publication_status: published
publisher: Springer
publist_id: '3229'
quality_controlled: '1'
scopus_import: 1
status: public
title: Persistent intersection homology
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2011'
...
---
_id: '3336'
abstract:
- lang: eng
text: 'We introduce TopoCut: a new way to integrate knowledge about topological
properties (TPs) into random field image segmentation model. Instead of including
TPs as additional constraints during minimization of the energy function, we devise
an efficient algorithm for modifying the unary potentials such that the resulting
segmentation is guaranteed with the desired properties. Our method is more flexible
in the sense that it handles more topology constraints than previous methods,
which were only able to enforce pairwise or global connectivity. In particular,
our method is very fast, making it for the first time possible to enforce global
topological properties in practical image segmentation tasks.'
acknowledgement: The first author is supported by the Austrian Science Fund (FWF)
grant No. P20134-N13. The authors would like to thank Sebastian Nowozin for helpful
discussions.
article_processing_charge: No
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Daniel
full_name: Freedman, Daniel
last_name: Freedman
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Chen C, Freedman D, Lampert C. Enforcing topological constraints in random
field image segmentation. In: CVPR: Computer Vision and Pattern Recognition.
IEEE; 2011:2089-2096. doi:10.1109/CVPR.2011.5995503'
apa: 'Chen, C., Freedman, D., & Lampert, C. (2011). Enforcing topological constraints
in random field image segmentation. In CVPR: Computer Vision and Pattern Recognition
(pp. 2089–2096). Colorado Springs, CO, United States: IEEE. https://doi.org/10.1109/CVPR.2011.5995503'
chicago: 'Chen, Chao, Daniel Freedman, and Christoph Lampert. “Enforcing Topological
Constraints in Random Field Image Segmentation.” In CVPR: Computer Vision and
Pattern Recognition, 2089–96. IEEE, 2011. https://doi.org/10.1109/CVPR.2011.5995503.'
ieee: 'C. Chen, D. Freedman, and C. Lampert, “Enforcing topological constraints
in random field image segmentation,” in CVPR: Computer Vision and Pattern Recognition,
Colorado Springs, CO, United States, 2011, pp. 2089–2096.'
ista: 'Chen C, Freedman D, Lampert C. 2011. Enforcing topological constraints in
random field image segmentation. CVPR: Computer Vision and Pattern Recognition.
CVPR: Conference on Computer Vision and Pattern Recognition, 2089–2096.'
mla: 'Chen, Chao, et al. “Enforcing Topological Constraints in Random Field Image
Segmentation.” CVPR: Computer Vision and Pattern Recognition, IEEE, 2011,
pp. 2089–96, doi:10.1109/CVPR.2011.5995503.'
short: 'C. Chen, D. Freedman, C. Lampert, in:, CVPR: Computer Vision and Pattern
Recognition, IEEE, 2011, pp. 2089–2096.'
conference:
end_date: 2011-06-25
location: Colorado Springs, CO, United States
name: 'CVPR: Conference on Computer Vision and Pattern Recognition'
start_date: 2011-06-20
date_created: 2018-12-11T12:02:45Z
date_published: 2011-07-22T00:00:00Z
date_updated: 2023-02-23T12:23:56Z
day: '22'
department:
- _id: HeEd
- _id: ChLa
doi: 10.1109/CVPR.2011.5995503
language:
- iso: eng
month: '07'
oa_version: None
page: 2089 - 2096
publication: 'CVPR: Computer Vision and Pattern Recognition'
publication_identifier:
eisbn:
- 978-1-4577-0395-9
isbn:
- 978-1-4577-0394-2
publication_status: published
publisher: IEEE
publist_id: '3294'
quality_controlled: '1'
related_material:
record:
- id: '5386'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Enforcing topological constraints in random field image segmentation
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '9648'
abstract:
- lang: eng
text: In this paper, we establish a correspondence between the incremental algorithm
for computing AT-models [8,9] and the one for computing persistent homology [6,14,15].
We also present a decremental algorithm for computing AT-models that allows to
extend the persistence computation to a wider setting. Finally, we show how to
combine incremental and decremental techniques for persistent homology computation.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Rocio
full_name: Gonzalez-Diaz, Rocio
last_name: Gonzalez-Diaz
- first_name: Adrian
full_name: Ion, Adrian
id: 29F89302-F248-11E8-B48F-1D18A9856A87
last_name: Ion
- first_name: Maria Jose
full_name: Jimenez, Maria Jose
last_name: Jimenez
- first_name: Regina
full_name: Poyatos, Regina
last_name: Poyatos
citation:
ama: 'Gonzalez-Diaz R, Ion A, Jimenez MJ, Poyatos R. Incremental-decremental algorithm
for computing AT-models and persistent homology. In: Computer Analysis of Images
and Patterns. Vol 6854. Springer Nature; 2011:286-293. doi:10.1007/978-3-642-23672-3_35'
apa: 'Gonzalez-Diaz, R., Ion, A., Jimenez, M. J., & Poyatos, R. (2011). Incremental-decremental
algorithm for computing AT-models and persistent homology. In Computer Analysis
of Images and Patterns (Vol. 6854, pp. 286–293). Seville, Spain: Springer
Nature. https://doi.org/10.1007/978-3-642-23672-3_35'
chicago: Gonzalez-Diaz, Rocio, Adrian Ion, Maria Jose Jimenez, and Regina Poyatos.
“Incremental-Decremental Algorithm for Computing AT-Models and Persistent Homology.”
In Computer Analysis of Images and Patterns, 6854:286–93. Springer Nature,
2011. https://doi.org/10.1007/978-3-642-23672-3_35.
ieee: R. Gonzalez-Diaz, A. Ion, M. J. Jimenez, and R. Poyatos, “Incremental-decremental
algorithm for computing AT-models and persistent homology,” in Computer Analysis
of Images and Patterns, Seville, Spain, 2011, vol. 6854, pp. 286–293.
ista: 'Gonzalez-Diaz R, Ion A, Jimenez MJ, Poyatos R. 2011. Incremental-decremental
algorithm for computing AT-models and persistent homology. Computer Analysis of
Images and Patterns. CAIP: International Conference on Computer Analysis of Images
and Patterns, LNCS, vol. 6854, 286–293.'
mla: Gonzalez-Diaz, Rocio, et al. “Incremental-Decremental Algorithm for Computing
AT-Models and Persistent Homology.” Computer Analysis of Images and Patterns,
vol. 6854, Springer Nature, 2011, pp. 286–93, doi:10.1007/978-3-642-23672-3_35.
short: R. Gonzalez-Diaz, A. Ion, M.J. Jimenez, R. Poyatos, in:, Computer Analysis
of Images and Patterns, Springer Nature, 2011, pp. 286–293.
conference:
end_date: 2011-08-31
location: Seville, Spain
name: 'CAIP: International Conference on Computer Analysis of Images and Patterns'
start_date: 2011-08-29
date_created: 2021-07-11T22:01:19Z
date_published: 2011-08-01T00:00:00Z
date_updated: 2021-08-12T13:53:17Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-642-23672-3_35
intvolume: ' 6854'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://hdl.handle.net/11441/30766
month: '08'
oa: 1
oa_version: Published Version
page: 286-293
publication: Computer Analysis of Images and Patterns
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783642236716'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Incremental-decremental algorithm for computing AT-models and persistent homology
type: conference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 6854
year: '2011'
...
---
_id: '10907'
abstract:
- lang: eng
text: This paper presents a method to create a model of an articulated object using
the planar motion in an initialization video. The model consists of rigid parts
connected by points of articulation. The rigid parts are described by the positions
of salient feature-points tracked throughout the video. Following a filtering
step that identifies points that belong to different objects, rigid parts are
found by a grouping process in a graph pyramid. Valid articulation points are
selected by verifying multiple hypotheses for each pair of parts.
acknowledgement: This work has been partially supported by the Austrian Science Fund
under grants S9103-N13 and P18716-N13.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicole M.
full_name: Artner, Nicole M.
last_name: Artner
- first_name: Adrian
full_name: Ion, Adrian
id: 29F89302-F248-11E8-B48F-1D18A9856A87
last_name: Ion
- first_name: Walter G.
full_name: Kropatsch, Walter G.
last_name: Kropatsch
citation:
ama: 'Artner NM, Ion A, Kropatsch WG. Spatio-temporal extraction of articulated
models in a graph pyramid. In: Jiang X, Ferrer M, Torsello A, eds. Graph-Based
Representations in Pattern Recognition. Vol 6658. LNIP. Berlin, Heidelberg:
Springer; 2011:215-224. doi:10.1007/978-3-642-20844-7_22'
apa: 'Artner, N. M., Ion, A., & Kropatsch, W. G. (2011). Spatio-temporal extraction
of articulated models in a graph pyramid. In X. Jiang, M. Ferrer, & A. Torsello
(Eds.), Graph-Based Representations in Pattern Recognition (Vol. 6658,
pp. 215–224). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-20844-7_22'
chicago: 'Artner, Nicole M., Adrian Ion, and Walter G. Kropatsch. “Spatio-Temporal
Extraction of Articulated Models in a Graph Pyramid.” In Graph-Based Representations
in Pattern Recognition, edited by Xiaoyi Jiang, Miquel Ferrer, and Andrea
Torsello, 6658:215–24. LNIP. Berlin, Heidelberg: Springer, 2011. https://doi.org/10.1007/978-3-642-20844-7_22.'
ieee: N. M. Artner, A. Ion, and W. G. Kropatsch, “Spatio-temporal extraction of
articulated models in a graph pyramid,” in Graph-Based Representations in Pattern
Recognition, Münster, Germany, 2011, vol. 6658, pp. 215–224.
ista: 'Artner NM, Ion A, Kropatsch WG. 2011. Spatio-temporal extraction of articulated
models in a graph pyramid. Graph-Based Representations in Pattern Recognition.
GbRPR: Graph-based Representations in Pattern RecognitionLNIP, LNCS, vol. 6658,
215–224.'
mla: Artner, Nicole M., et al. “Spatio-Temporal Extraction of Articulated Models
in a Graph Pyramid.” Graph-Based Representations in Pattern Recognition,
edited by Xiaoyi Jiang et al., vol. 6658, Springer, 2011, pp. 215–24, doi:10.1007/978-3-642-20844-7_22.
short: N.M. Artner, A. Ion, W.G. Kropatsch, in:, X. Jiang, M. Ferrer, A. Torsello
(Eds.), Graph-Based Representations in Pattern Recognition, Springer, Berlin,
Heidelberg, 2011, pp. 215–224.
conference:
end_date: 2011-05-20
location: Münster, Germany
name: 'GbRPR: Graph-based Representations in Pattern Recognition'
start_date: 2011-05-18
date_created: 2022-03-21T08:08:35Z
date_published: 2011-06-01T00:00:00Z
date_updated: 2023-09-05T14:10:15Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-642-20844-7_22
editor:
- first_name: Xiaoyi
full_name: Jiang, Xiaoyi
last_name: Jiang
- first_name: Miquel
full_name: Ferrer, Miquel
last_name: Ferrer
- first_name: Andrea
full_name: Torsello, Andrea
last_name: Torsello
intvolume: ' 6658'
language:
- iso: eng
month: '06'
oa_version: None
page: 215-224
place: Berlin, Heidelberg
publication: Graph-Based Representations in Pattern Recognition
publication_identifier:
eisbn:
- '9783642208447'
eissn:
- 1611-3349
isbn:
- '9783642208430'
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
series_title: LNIP
status: public
title: Spatio-temporal extraction of articulated models in a graph pyramid
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 6658
year: '2011'
...
---
_id: '10909'
abstract:
- lang: eng
text: We address the problem of localizing homology classes, namely, finding the
cycle representing a given class with the most concise geometric measure. We focus
on the volume measure, that is, the 1-norm of a cycle. Two main results are presented.
First, we prove the problem is NP-hard to approximate within any constant factor.
Second, we prove that for homology of dimension two or higher, the problem is
NP-hard to approximate even when the Betti number is O(1). A side effect is the
inapproximability of the problem of computing the nonbounding cycle with the smallest
volume, and computing cycles representing a homology basis with the minimal total
volume. We also discuss other geometric measures (diameter and radius) and show
their disadvantages in homology localization. Our work is restricted to homology
over the ℤ2 field.
acknowledgement: Partially supported by the Austrian Science Fund under grantFSP-S9103-N04
and P20134-N13.
article_processing_charge: No
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Daniel
full_name: Freedman, Daniel
last_name: Freedman
citation:
ama: 'Chen C, Freedman D. Hardness results for homology localization. In: Proceedings
of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms. Society for
Industrial and Applied Mathematics; 2010:1594-1604. doi:10.1137/1.9781611973075.129'
apa: 'Chen, C., & Freedman, D. (2010). Hardness results for homology localization.
In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms
(pp. 1594–1604). Austin, TX, United States: Society for Industrial and Applied
Mathematics. https://doi.org/10.1137/1.9781611973075.129'
chicago: Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.”
In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms,
1594–1604. Society for Industrial and Applied Mathematics, 2010. https://doi.org/10.1137/1.9781611973075.129.
ieee: C. Chen and D. Freedman, “Hardness results for homology localization,” in
Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms,
Austin, TX, United States, 2010, pp. 1594–1604.
ista: 'Chen C, Freedman D. 2010. Hardness results for homology localization. Proceedings
of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium
on Discrete Algorithms, 1594–1604.'
mla: Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.”
Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms,
Society for Industrial and Applied Mathematics, 2010, pp. 1594–604, doi:10.1137/1.9781611973075.129.
short: C. Chen, D. Freedman, in:, Proceedings of the 2010 Annual ACM-SIAM Symposium
on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2010,
pp. 1594–1604.
conference:
end_date: 2010-01-19
location: Austin, TX, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2010-01-17
date_created: 2022-03-21T08:24:07Z
date_published: 2010-02-01T00:00:00Z
date_updated: 2023-02-23T11:19:46Z
day: '01'
department:
- _id: HeEd
doi: 10.1137/1.9781611973075.129
language:
- iso: eng
month: '02'
oa_version: None
page: 1594-1604
publication: Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- '9781611973075'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '3267'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Hardness results for homology localization
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2010'
...
---
_id: '3782'
abstract:
- lang: eng
text: In cortex surface segmentation, the extracted surface is required to have
a particular topology, namely, a two-sphere. We present a new method for removing
topology noise of a curve or surface within the level set framework, and thus
produce a cortical surface with correct topology. We define a new energy term
which quantifies topology noise. We then show how to minimize this term by computing
its functional derivative with respect to the level set function. This method
differs from existing methods in that it is inherently continuous and not digital;
and in the way that our energy directly relates to the topology of the underlying
curve or surface, versus existing knot-based measures which are related in a more
indirect fashion. The proposed flow is validated empirically.
acknowledgement: "Partially supported by the Austri an Science Fund unde r grant P20134-N13.\r\nWe
thank Helena Molina-Abril for very helpful discussion. We thank anonymous reviewers
for helpful comments."
alternative_title:
- LNCS
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Daniel
full_name: Freedman, Daniel
last_name: Freedman
citation:
ama: 'Chen C, Freedman D. Topology noise removal for curve and surface evolution.
In: Conference Proceedings MCV 2010. Vol 6533. Springer; 2010:31-42. doi:10.1007/978-3-642-18421-5_4'
apa: 'Chen, C., & Freedman, D. (2010). Topology noise removal for curve and
surface evolution. In Conference proceedings MCV 2010 (Vol. 6533, pp.
31–42). Beijing, China: Springer. https://doi.org/10.1007/978-3-642-18421-5_4'
chicago: Chen, Chao, and Daniel Freedman. “Topology Noise Removal for Curve and
Surface Evolution.” In Conference Proceedings MCV 2010, 6533:31–42. Springer,
2010. https://doi.org/10.1007/978-3-642-18421-5_4.
ieee: C. Chen and D. Freedman, “Topology noise removal for curve and surface evolution,”
in Conference proceedings MCV 2010, Beijing, China, 2010, vol. 6533, pp.
31–42.
ista: 'Chen C, Freedman D. 2010. Topology noise removal for curve and surface evolution. Conference
proceedings MCV 2010. MCV: Medical Computer Vision, LNCS, vol. 6533, 31–42.'
mla: Chen, Chao, and Daniel Freedman. “Topology Noise Removal for Curve and Surface
Evolution.” Conference Proceedings MCV 2010, vol. 6533, Springer, 2010,
pp. 31–42, doi:10.1007/978-3-642-18421-5_4.
short: C. Chen, D. Freedman, in:, Conference Proceedings MCV 2010, Springer, 2010,
pp. 31–42.
conference:
end_date: 2010-09-20
location: Beijing, China
name: 'MCV: Medical Computer Vision'
start_date: 2010-09-20
date_created: 2018-12-11T12:05:08Z
date_published: 2010-12-31T00:00:00Z
date_updated: 2021-01-12T07:52:10Z
day: '31'
department:
- _id: HeEd
doi: 10.1007/978-3-642-18421-5_4
intvolume: ' 6533'
language:
- iso: eng
month: '12'
oa_version: None
page: 31 - 42
publication: ' Conference proceedings MCV 2010'
publication_status: published
publisher: Springer
publist_id: '2445'
quality_controlled: '1'
scopus_import: 1
status: public
title: Topology noise removal for curve and surface evolution
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 6533
year: '2010'
...
---
_id: '3795'
abstract:
- lang: eng
text: 'The (apparent) contour of a smooth mapping from a 2-manifold to the plane,
f: M → R2 , is the set of critical values, that is, the image of the points at
which the gradients of the two component functions are linearly dependent. Assuming
M is compact and orientable and measuring difference with the erosion distance,
we prove that the contour is stable.'
acknowledgement: This research is partially supported by the Defense Advanced Research
Projects Agency (DARPA) under grants HR0011-05-1-0007 and HR0011-05-1-0057.
alternative_title:
- Mathematics and Visualization
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Dmitriy
full_name: Morozov, Dmitriy
last_name: Morozov
- first_name: Amit
full_name: Patel, Amit
id: 34A254A0-F248-11E8-B48F-1D18A9856A87
last_name: Patel
citation:
ama: 'Edelsbrunner H, Morozov D, Patel A. The stability of the apparent contour
of an orientable 2-manifold. In: Topological Data Analysis and Visualization:
Theory, Algorithms and Applications. Springer; 2010:27-42. doi:10.1007/978-3-642-15014-2_3'
apa: 'Edelsbrunner, H., Morozov, D., & Patel, A. (2010). The stability of the
apparent contour of an orientable 2-manifold. In Topological Data Analysis
and Visualization: Theory, Algorithms and Applications (pp. 27–42). Springer.
https://doi.org/10.1007/978-3-642-15014-2_3'
chicago: 'Edelsbrunner, Herbert, Dmitriy Morozov, and Amit Patel. “The Stability
of the Apparent Contour of an Orientable 2-Manifold.” In Topological Data Analysis
and Visualization: Theory, Algorithms and Applications, 27–42. Springer, 2010.
https://doi.org/10.1007/978-3-642-15014-2_3.'
ieee: 'H. Edelsbrunner, D. Morozov, and A. Patel, “The stability of the apparent
contour of an orientable 2-manifold,” in Topological Data Analysis and Visualization:
Theory, Algorithms and Applications, Springer, 2010, pp. 27–42.'
ista: 'Edelsbrunner H, Morozov D, Patel A. 2010.The stability of the apparent contour
of an orientable 2-manifold. In: Topological Data Analysis and Visualization:
Theory, Algorithms and Applications. Mathematics and Visualization, , 27–42.'
mla: 'Edelsbrunner, Herbert, et al. “The Stability of the Apparent Contour of an
Orientable 2-Manifold.” Topological Data Analysis and Visualization: Theory,
Algorithms and Applications, Springer, 2010, pp. 27–42, doi:10.1007/978-3-642-15014-2_3.'
short: 'H. Edelsbrunner, D. Morozov, A. Patel, in:, Topological Data Analysis and
Visualization: Theory, Algorithms and Applications, Springer, 2010, pp. 27–42.'
date_created: 2018-12-11T12:05:13Z
date_published: 2010-12-22T00:00:00Z
date_updated: 2021-01-12T07:52:15Z
day: '22'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/978-3-642-15014-2_3
file:
- access_level: open_access
checksum: f03a44c3d1c3e2d4fedb3b94404f3fd5
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:40Z
date_updated: 2020-07-14T12:46:16Z
file_id: '4896'
file_name: IST-2016-538-v1+1_2011-B-02-ApparentContour.pdf
file_size: 210710
relation: main_file
file_date_updated: 2020-07-14T12:46:16Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
page: 27 - 42
publication: 'Topological Data Analysis and Visualization: Theory, Algorithms and
Applications'
publication_status: published
publisher: Springer
publist_id: '2428'
pubrep_id: '538'
quality_controlled: '1'
scopus_import: 1
status: public
title: The stability of the apparent contour of an orientable 2-manifold
type: book_chapter
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2010'
...
---
_id: '3848'
abstract:
- lang: eng
text: We define the robustness of a level set homology class of a function f:XR
as the magnitude of a perturbation necessary to kill the class. Casting this notion
into a group theoretic framework, we compute the robustness for each class, using
a connection to extended persistent homology. The special case X=R3 has ramifications
in medical imaging and scientific visualization.
alternative_title:
- LNCS
author:
- first_name: Paul
full_name: Bendich, Paul
id: 43F6EC54-F248-11E8-B48F-1D18A9856A87
last_name: Bendich
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Dmitriy
full_name: Morozov, Dmitriy
last_name: Morozov
- first_name: Amit
full_name: Patel, Amit
id: 34A254A0-F248-11E8-B48F-1D18A9856A87
last_name: Patel
citation:
ama: 'Bendich P, Edelsbrunner H, Morozov D, Patel A. The robustness of level sets.
In: Vol 6346. Springer; 2010:1-10. doi:10.1007/978-3-642-15775-2_1'
apa: 'Bendich, P., Edelsbrunner, H., Morozov, D., & Patel, A. (2010). The robustness
of level sets (Vol. 6346, pp. 1–10). Presented at the ESA: European Symposium
on Algorithms, Liverpool, UK: Springer. https://doi.org/10.1007/978-3-642-15775-2_1'
chicago: Bendich, Paul, Herbert Edelsbrunner, Dmitriy Morozov, and Amit Patel. “The
Robustness of Level Sets,” 6346:1–10. Springer, 2010. https://doi.org/10.1007/978-3-642-15775-2_1.
ieee: 'P. Bendich, H. Edelsbrunner, D. Morozov, and A. Patel, “The robustness of
level sets,” presented at the ESA: European Symposium on Algorithms, Liverpool,
UK, 2010, vol. 6346, pp. 1–10.'
ista: 'Bendich P, Edelsbrunner H, Morozov D, Patel A. 2010. The robustness of level
sets. ESA: European Symposium on Algorithms, LNCS, vol. 6346, 1–10.'
mla: Bendich, Paul, et al. The Robustness of Level Sets. Vol. 6346, Springer,
2010, pp. 1–10, doi:10.1007/978-3-642-15775-2_1.
short: P. Bendich, H. Edelsbrunner, D. Morozov, A. Patel, in:, Springer, 2010, pp.
1–10.
conference:
end_date: 2010-09-08
location: Liverpool, UK
name: 'ESA: European Symposium on Algorithms'
start_date: 2010-09-06
date_created: 2018-12-11T12:05:30Z
date_published: 2010-09-01T00:00:00Z
date_updated: 2021-01-12T07:52:38Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-642-15775-2_1
intvolume: ' 6346'
language:
- iso: eng
month: '09'
oa_version: None
page: 1 - 10
publication_status: published
publisher: Springer
publist_id: '2336'
quality_controlled: '1'
scopus_import: 1
status: public
title: The robustness of level sets
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6346
year: '2010'
...
---
_id: '3853'
abstract:
- lang: eng
text: '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.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Philippe
full_name: Rannou, Philippe
last_name: Rannou
citation:
ama: 'Chatterjee K, Doyen L, Edelsbrunner H, Henzinger TA, Rannou P. Mean-payoff
automaton expressions. In: Vol 6269. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2010:269-283. doi:10.1007/978-3-642-15375-4_19'
apa: 'Chatterjee, K., Doyen, L., Edelsbrunner, H., Henzinger, T. A., & Rannou,
P. (2010). Mean-payoff automaton expressions (Vol. 6269, pp. 269–283). Presented
at the CONCUR: Concurrency Theory, Paris, France: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.1007/978-3-642-15375-4_19'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Herbert Edelsbrunner, Thomas A Henzinger,
and Philippe Rannou. “Mean-Payoff Automaton Expressions,” 6269:269–83. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2010. https://doi.org/10.1007/978-3-642-15375-4_19.
ieee: 'K. Chatterjee, L. Doyen, H. Edelsbrunner, T. A. Henzinger, and P. Rannou,
“Mean-payoff automaton expressions,” presented at the CONCUR: Concurrency Theory,
Paris, France, 2010, vol. 6269, pp. 269–283.'
ista: 'Chatterjee K, Doyen L, Edelsbrunner H, Henzinger TA, Rannou P. 2010. Mean-payoff
automaton expressions. CONCUR: Concurrency Theory, LNCS, vol. 6269, 269–283.'
mla: Chatterjee, Krishnendu, et al. Mean-Payoff Automaton Expressions. Vol.
6269, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 269–83, doi:10.1007/978-3-642-15375-4_19.
short: K. Chatterjee, L. Doyen, H. Edelsbrunner, T.A. Henzinger, P. Rannou, in:,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 269–283.
conference:
end_date: 2010-09-03
location: Paris, France
name: 'CONCUR: Concurrency Theory'
start_date: 2010-08-31
date_created: 2018-12-11T12:05:31Z
date_published: 2010-11-18T00:00:00Z
date_updated: 2021-01-12T07:52:40Z
day: '18'
ddc:
- '000'
- '005'
department:
- _id: KrCh
- _id: HeEd
- _id: ToHe
doi: 10.1007/978-3-642-15375-4_19
ec_funded: 1
file:
- access_level: open_access
checksum: 4f753ae99d076553fb8733e2c8b390e2
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:41Z
date_updated: 2020-07-14T12:46:17Z
file_id: '5163'
file_name: IST-2012-62-v1+1_Mean-payoff_automaton_expressions.pdf
file_size: 233260
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
intvolume: ' 6269'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Submitted Version
page: 269 - 283
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '2328'
pubrep_id: '62'
quality_controlled: '1'
scopus_import: 1
status: public
title: Mean-payoff automaton expressions
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6269
year: '2010'
...
---
_id: '3849'
abstract:
- lang: eng
text: Using ideas from persistent homology, the robustness of a level set of a real-valued
function is defined in terms of the magnitude of the perturbation necessary to
kill the classes. Prior work has shown that the homology and robustness information
can be read off the extended persistence diagram of the function. This paper extends
these results to a non-uniform error model in which perturbations vary in their
magnitude across the domain.
alternative_title:
- LNCS
author:
- first_name: Paul
full_name: Bendich, Paul
id: 43F6EC54-F248-11E8-B48F-1D18A9856A87
last_name: Bendich
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Amit
full_name: Patel, Amit
id: 34A254A0-F248-11E8-B48F-1D18A9856A87
last_name: Patel
citation:
ama: 'Bendich P, Edelsbrunner H, Kerber M, Patel A. Persistent homology under non-uniform
error. In: Vol 6281. Springer; 2010:12-23. doi:10.1007/978-3-642-15155-2_2'
apa: 'Bendich, P., Edelsbrunner, H., Kerber, M., & Patel, A. (2010). Persistent
homology under non-uniform error (Vol. 6281, pp. 12–23). Presented at the MFCS:
Mathematical Foundations of Computer Science, Brno, Czech Republic: Springer.
https://doi.org/10.1007/978-3-642-15155-2_2'
chicago: Bendich, Paul, Herbert Edelsbrunner, Michael Kerber, and Amit Patel. “Persistent
Homology under Non-Uniform Error,” 6281:12–23. Springer, 2010. https://doi.org/10.1007/978-3-642-15155-2_2.
ieee: 'P. Bendich, H. Edelsbrunner, M. Kerber, and A. Patel, “Persistent homology
under non-uniform error,” presented at the MFCS: Mathematical Foundations of Computer
Science, Brno, Czech Republic, 2010, vol. 6281, pp. 12–23.'
ista: 'Bendich P, Edelsbrunner H, Kerber M, Patel A. 2010. Persistent homology under
non-uniform error. MFCS: Mathematical Foundations of Computer Science, LNCS, vol.
6281, 12–23.'
mla: Bendich, Paul, et al. Persistent Homology under Non-Uniform Error. Vol.
6281, Springer, 2010, pp. 12–23, doi:10.1007/978-3-642-15155-2_2.
short: P. Bendich, H. Edelsbrunner, M. Kerber, A. Patel, in:, Springer, 2010, pp.
12–23.
conference:
end_date: 2010-08-27
location: Brno, Czech Republic
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2010-08-23
date_created: 2018-12-11T12:05:30Z
date_published: 2010-08-10T00:00:00Z
date_updated: 2021-01-12T07:52:38Z
day: '10'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/978-3-642-15155-2_2
file:
- access_level: open_access
checksum: af61e1c2bb42f3d556179d4692caeb1b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:13Z
date_updated: 2020-07-14T12:46:17Z
file_id: '4994'
file_name: IST-2016-537-v1+1_2010-P-05-NonuniformError.pdf
file_size: 142357
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
intvolume: ' 6281'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 12 - 23
publication_status: published
publisher: Springer
publist_id: '2333'
pubrep_id: '537'
quality_controlled: '1'
scopus_import: 1
status: public
title: Persistent homology under non-uniform error
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6281
year: '2010'
...
---
_id: '3850'
abstract:
- lang: eng
text: 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:
- first_name: Eric
full_name: Berberich, Eric
last_name: Berberich
- first_name: Dan
full_name: Halperin, Dan
last_name: Halperin
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Roza
full_name: Pogalnikova, Roza
last_name: Pogalnikova
citation:
ama: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. Polygonal reconstruction
from approximate offsets. In: TU Dortmund; 2010:12-23.'
apa: 'Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2010). Polygonal
reconstruction from approximate offsets (pp. 12–23). Presented at the EuroCG:
European Workshop on Computational Geometry, Dortmund, Germany: TU Dortmund.'
chicago: Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Polygonal
Reconstruction from Approximate Offsets,” 12–23. TU Dortmund, 2010.
ieee: 'E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Polygonal reconstruction
from approximate offsets,” presented at the EuroCG: European Workshop on Computational
Geometry, Dortmund, Germany, 2010, pp. 12–23.'
ista: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. 2010. Polygonal reconstruction
from approximate offsets. EuroCG: European Workshop on Computational Geometry,
12–23.'
mla: Berberich, Eric, et al. Polygonal Reconstruction from Approximate Offsets.
TU Dortmund, 2010, pp. 12–23.
short: E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, TU Dortmund, 2010,
pp. 12–23.
conference:
end_date: 2010-03-24
location: Dortmund, Germany
name: 'EuroCG: European Workshop on Computational Geometry'
start_date: 2010-03-22
date_created: 2018-12-11T12:05:30Z
date_published: 2010-01-01T00:00:00Z
date_updated: 2021-01-12T07:52:39Z
day: '01'
department:
- _id: HeEd
language:
- iso: eng
month: '01'
oa_version: None
page: 12 - 23
publication_status: published
publisher: TU Dortmund
publist_id: '2334'
quality_controlled: '1'
status: public
title: Polygonal reconstruction from approximate offsets
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2010'
...
---
_id: '3901'
abstract:
- lang: eng
text: 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:
- first_name: Paul
full_name: Bendich, Paul
id: 43F6EC54-F248-11E8-B48F-1D18A9856A87
last_name: Bendich
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: Bendich P, Edelsbrunner H, Kerber M. Computing robustness and persistence for
images. IEEE Transactions of Visualization and Computer Graphics. 2010;16(6):1251-1260.
doi:10.1109/TVCG.2010.139
apa: Bendich, P., Edelsbrunner, H., & Kerber, M. (2010). Computing robustness
and persistence for images. IEEE Transactions of Visualization and Computer
Graphics. IEEE. https://doi.org/10.1109/TVCG.2010.139
chicago: Bendich, Paul, Herbert Edelsbrunner, and Michael Kerber. “Computing Robustness
and Persistence for Images.” IEEE Transactions of Visualization and Computer
Graphics. IEEE, 2010. https://doi.org/10.1109/TVCG.2010.139.
ieee: P. Bendich, H. Edelsbrunner, and M. Kerber, “Computing robustness and persistence
for images,” IEEE Transactions of Visualization and Computer Graphics,
vol. 16, no. 6. IEEE, pp. 1251–1260, 2010.
ista: Bendich P, Edelsbrunner H, Kerber M. 2010. Computing robustness and persistence
for images. IEEE Transactions of Visualization and Computer Graphics. 16(6), 1251–1260.
mla: Bendich, Paul, et al. “Computing Robustness and Persistence for Images.” IEEE
Transactions of Visualization and Computer Graphics, vol. 16, no. 6, IEEE,
2010, pp. 1251–60, doi:10.1109/TVCG.2010.139.
short: P. Bendich, H. Edelsbrunner, M. Kerber, IEEE Transactions of Visualization
and Computer Graphics 16 (2010) 1251–1260.
date_created: 2018-12-11T12:05:47Z
date_published: 2010-10-28T00:00:00Z
date_updated: 2021-01-12T07:53:04Z
day: '28'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1109/TVCG.2010.139
file:
- access_level: open_access
checksum: f6d813c04f4b46023cec6b9a17f15472
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:10Z
date_updated: 2020-07-14T12:46:21Z
file_id: '5262'
file_name: IST-2016-536-v1+1_2010-J-02-PersistenceforImages.pdf
file_size: 721994
relation: main_file
file_date_updated: 2020-07-14T12:46:21Z
has_accepted_license: '1'
intvolume: ' 16'
issue: '6'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 1251 - 1260
publication: IEEE Transactions of Visualization and Computer Graphics
publication_status: published
publisher: IEEE
publist_id: '2253'
pubrep_id: '536'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computing robustness and persistence for images
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2010'
...
---
_id: '3968'
abstract:
- lang: eng
text: 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.
acknowledgement: This research was partially supported by Geomagic, Inc., and by the
Defense Advanced Research Projects Agency (DARPA) under grants HR0011-05-1-0007
and HR0011-05-1-0057.
alternative_title:
- LNCS
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: John
full_name: Harer, John
last_name: Harer
citation:
ama: 'Edelsbrunner H, Harer J. The persistent Morse complex segmentation of a 3-manifold.
In: Vol 5903. Springer; 2009:36-50. doi:10.1007/978-3-642-10470-1_4'
apa: 'Edelsbrunner, H., & Harer, J. (2009). The persistent Morse complex segmentation
of a 3-manifold (Vol. 5903, pp. 36–50). Presented at the 3DPH: Modelling the Physiological
Human, Zermatt, Switzerland: Springer. https://doi.org/10.1007/978-3-642-10470-1_4'
chicago: Edelsbrunner, Herbert, and John Harer. “The Persistent Morse Complex Segmentation
of a 3-Manifold,” 5903:36–50. Springer, 2009. https://doi.org/10.1007/978-3-642-10470-1_4.
ieee: 'H. Edelsbrunner and J. Harer, “The persistent Morse complex segmentation
of a 3-manifold,” presented at the 3DPH: Modelling the Physiological Human, Zermatt,
Switzerland, 2009, vol. 5903, pp. 36–50.'
ista: 'Edelsbrunner H, Harer J. 2009. The persistent Morse complex segmentation
of a 3-manifold. 3DPH: Modelling the Physiological Human, LNCS, vol. 5903, 36–50.'
mla: Edelsbrunner, Herbert, and John Harer. The Persistent Morse Complex Segmentation
of a 3-Manifold. Vol. 5903, Springer, 2009, pp. 36–50, doi:10.1007/978-3-642-10470-1_4.
short: H. Edelsbrunner, J. Harer, in:, Springer, 2009, pp. 36–50.
conference:
end_date: 2009-12-02
location: Zermatt, Switzerland
name: '3DPH: Modelling the Physiological Human'
start_date: 2009-11-29
date_created: 2018-12-11T12:06:10Z
date_published: 2009-11-17T00:00:00Z
date_updated: 2021-01-12T07:53:32Z
day: '17'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/978-3-642-10470-1_4
file:
- access_level: open_access
checksum: 11fc85bcc19bab1f020e706a4b8a4660
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:33Z
date_updated: 2020-07-14T12:46:21Z
file_id: '4694'
file_name: IST-2016-535-v1+1_2009-P-04-3ManifoldSegmentation.pdf
file_size: 165090
relation: main_file
file_date_updated: 2020-07-14T12:46:21Z
has_accepted_license: '1'
intvolume: ' 5903'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Submitted Version
page: 36 - 50
publication_status: published
publisher: Springer
publist_id: '2160'
pubrep_id: '535'
quality_controlled: '1'
scopus_import: 1
status: public
title: The persistent Morse complex segmentation of a 3-manifold
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5903
year: '2009'
...