---
_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: '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: '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: '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: '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: '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: '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: '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: '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'
...