---
_id: '2901'
abstract:
- lang: eng
text: ' We introduce the M-modes problem for graphical models: predicting the M
label configurations of highest probability that are at the same time local maxima
of the probability landscape. M-modes have multiple possible applications: because
they are intrinsically diverse, they provide a principled alternative to non-maximum
suppression techniques for structured prediction, they can act as codebook vectors
for quantizing the configuration space, or they can form component centers for
mixture model approximation. We present two algorithms for solving the M-modes
problem. The first algorithm solves the problem in polynomial time when the underlying
graphical model is a simple chain. The second algorithm solves the problem for
junction chains. In synthetic and real dataset, we demonstrate how M-modes can
improve the performance of prediction. We also use the generated modes as a tool
to understand the topography of the probability distribution of configurations,
for example with relation to the training set size and amount of noise in the
data. '
alternative_title:
- ' JMLR: W&CP'
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Zhu
full_name: Yan, Zhu
last_name: Yan
- first_name: Dimitris
full_name: Metaxas, Dimitris
last_name: Metaxas
- 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, Kolmogorov V, Yan Z, Metaxas D, Lampert C. Computing the M most probable
modes of a graphical model. In: Vol 31. JMLR; 2013:161-169.'
apa: 'Chen, C., Kolmogorov, V., Yan, Z., Metaxas, D., & Lampert, C. (2013).
Computing the M most probable modes of a graphical model (Vol. 31, pp. 161–169).
Presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence,
Scottsdale, AZ, United States: JMLR.'
chicago: Chen, Chao, Vladimir Kolmogorov, Zhu Yan, Dimitris Metaxas, and Christoph
Lampert. “Computing the M Most Probable Modes of a Graphical Model,” 31:161–69.
JMLR, 2013.
ieee: 'C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, and C. Lampert, “Computing the
M most probable modes of a graphical model,” presented at the AISTATS: Conference
on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States, 2013,
vol. 31, pp. 161–169.'
ista: 'Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. 2013. Computing the M
most probable modes of a graphical model. AISTATS: Conference on Uncertainty
in Artificial Intelligence, JMLR: W&CP, vol. 31, 161–169.'
mla: Chen, Chao, et al. *Computing the M Most Probable Modes of a Graphical Model*.
Vol. 31, JMLR, 2013, pp. 161–69.
short: C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, C. Lampert, in:, JMLR, 2013,
pp. 161–169.
conference:
end_date: 2013-05-01
location: Scottsdale, AZ, United States
name: ' AISTATS: Conference on Uncertainty in Artificial Intelligence'
start_date: 2013-04-29
date_created: 2018-12-11T12:00:14Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T07:00:35Z
day: '01'
department:
- _id: HeEd
- _id: VlKo
- _id: ChLa
intvolume: ' 31'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://jmlr.org/proceedings/papers/v31/chen13a.html
month: '01'
oa: 1
oa_version: None
page: 161 - 169
publication_status: published
publisher: JMLR
publist_id: '3846'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computing the M most probable modes of a graphical model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 31
year: '2013'
...
---
_id: '2906'
abstract:
- lang: eng
text: "Motivated by an application in cell biology, we describe an extension of
the kinetic data structures framework from Delaunay triangulations to fixed-radius
alpha complexes. Our algorithm is implemented\r\nusing CGAL, following the exact
geometric computation paradigm. We report on several\r\ntechniques to accelerate
the computation that turn our implementation applicable to the underlying biological\r\nproblem."
alternative_title:
- ALENEX
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Kerber M, Edelsbrunner H. 3D kinetic alpha complexes and their implementation.
In: *2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments*.
Society of Industrial and Applied Mathematics; 2013:70-77. doi:10.1137/1.9781611972931.6'
apa: 'Kerber, M., & Edelsbrunner, H. (2013). 3D kinetic alpha complexes and
their implementation. In *2013 Proceedings of the 15th Workshop on Algorithm
Engineering and Experiments* (pp. 70–77). New Orleans, LA, United States: Society
of Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611972931.6'
chicago: Kerber, Michael, and Herbert Edelsbrunner. “3D Kinetic Alpha Complexes
and Their Implementation.” In *2013 Proceedings of the 15th Workshop on Algorithm
Engineering and Experiments*, 70–77. Society of Industrial and Applied Mathematics,
2013. https://doi.org/10.1137/1.9781611972931.6.
ieee: M. Kerber and H. Edelsbrunner, “3D kinetic alpha complexes and their implementation,”
in *2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments*,
New Orleans, LA, United States, 2013, pp. 70–77.
ista: 'Kerber M, Edelsbrunner H. 2013. 3D kinetic alpha complexes and their implementation.
2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments.
ALENEX: Algorithm Engineering and Experiments, ALENEX, , 70–77.'
mla: Kerber, Michael, and Herbert Edelsbrunner. “3D Kinetic Alpha Complexes and
Their Implementation.” *2013 Proceedings of the 15th Workshop on Algorithm Engineering
and Experiments*, Society of Industrial and Applied Mathematics, 2013, pp.
70–77, doi:10.1137/1.9781611972931.6.
short: M. Kerber, H. Edelsbrunner, in:, 2013 Proceedings of the 15th Workshop on
Algorithm Engineering and Experiments, Society of Industrial and Applied Mathematics,
2013, pp. 70–77.
conference:
end_date: 2013-01-07
location: New Orleans, LA, United States
name: 'ALENEX: Algorithm Engineering and Experiments'
start_date: 2013-01-07
date_created: 2018-12-11T12:00:16Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T07:00:36Z
day: '01'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.1137/1.9781611972931.6
file:
- access_level: open_access
checksum: a15a3ba22df9445731507f3e06c9fcee
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:57Z
date_updated: 2020-07-14T12:45:52Z
file_id: '4720'
file_name: IST-2016-547-v1+1_2013-P-08-MedusaII.pdf
file_size: 403013
relation: main_file
file_date_updated: 2020-07-14T12:45:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 70 - 77
publication: 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments
publication_status: published
publisher: Society of Industrial and Applied Mathematics
publist_id: '3841'
pubrep_id: '547'
quality_controlled: '1'
scopus_import: 1
status: public
title: 3D kinetic alpha complexes and their implementation
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2939'
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 d (n) log n), where C (1 - δ) Γ is the number
of homology classes with persistence at least (1 - δ) Γ, n is the total number
of simplices in the complex, d its dimension, and R d (n) is the complexity of
computing the rank of an n × n matrix with O (d n) nonzero entries. Depending
on the choice of the rank algorithm, this yields a deterministic O (C (1 - δ)
Γ n 2.376) algorithm, an O (C (1 - δ) Γ n 2.28) Las-Vegas algorithm, or an O (C
(1 - δ) Γ n 2 + ε{lunate}) Monte-Carlo algorithm for an arbitrary ε{lunate} >
0. The space complexity of the Monte-Carlo version is bounded by O (d n) = O (n
log n).
acknowledgement: The authors thank Herbert Edelsbrunner for many helpful discussions
and suggestions. Moreover, they are grateful for the careful reviews that helped
to improve the quality of the paper.
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. *Computational
Geometry: Theory and Applications*. 2013;46(4):435-447. doi:10.1016/j.comgeo.2012.02.010'
apa: 'Chen, C., & Kerber, M. (2013). An output sensitive algorithm for persistent
homology. *Computational Geometry: Theory and Applications*. Elsevier. https://doi.org/10.1016/j.comgeo.2012.02.010'
chicago: 'Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent
Homology.” *Computational Geometry: Theory and Applications*. Elsevier, 2013.
https://doi.org/10.1016/j.comgeo.2012.02.010.'
ieee: 'C. Chen and M. Kerber, “An output sensitive algorithm for persistent homology,”
*Computational Geometry: Theory and Applications*, vol. 46, no. 4. Elsevier,
pp. 435–447, 2013.'
ista: 'Chen C, Kerber M. 2013. An output sensitive algorithm for persistent homology.
Computational Geometry: Theory and Applications. 46(4), 435–447.'
mla: 'Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent
Homology.” *Computational Geometry: Theory and Applications*, vol. 46, no.
4, Elsevier, 2013, pp. 435–47, doi:10.1016/j.comgeo.2012.02.010.'
short: 'C. Chen, M. Kerber, Computational Geometry: Theory and Applications 46 (2013)
435–447.'
date_created: 2018-12-11T12:00:27Z
date_published: 2013-05-01T00:00:00Z
date_updated: 2021-01-12T07:42:59Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2012.02.010
intvolume: ' 46'
issue: '4'
language:
- iso: eng
month: '05'
oa_version: None
page: 435 - 447
publication: 'Computational Geometry: Theory and Applications'
publication_status: published
publisher: Elsevier
publist_id: '3796'
quality_controlled: '1'
related_material:
record:
- id: '3367'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: An output sensitive algorithm for persistent homology
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 46
year: '2013'
...
---
_id: '2209'
abstract:
- lang: eng
text: "A straight skeleton is a well-known geometric structure, and several algorithms
exist to construct the straight skeleton for a given polygon or planar straight-line
graph. In this paper, we ask the reverse question: Given the straight skeleton
(in form of a planar straight-line graph, with some rays to infinity), can we
reconstruct a planar straight-line graph for which this was the straight skeleton?
We show how to reduce this problem to the problem of finding a line that intersects
a set of convex polygons. We can find these convex polygons and all such lines
in $O(nlog n)$ time in the Real RAM computer model, where $n$ denotes the number
of edges of the input graph. We also explain how our approach can be used for
recognizing Voronoi diagrams of points, thereby completing a partial solution
provided by Ash and Bolker in 1985.\r\n"
alternative_title:
- '2013 10th International Symposium on Voronoi Diagrams in Science and Engineering
(ISVD 2013) '
author:
- first_name: Therese
full_name: Biedl, Therese
last_name: Biedl
- first_name: Martin
full_name: Held, Martin
last_name: Held
- first_name: Stefan
full_name: Huber, Stefan
id: 4700A070-F248-11E8-B48F-1D18A9856A87
last_name: Huber
orcid: 0000-0002-8871-5814
citation:
ama: 'Biedl T, Held M, Huber S. Recognizing straight skeletons and Voronoi diagrams
and reconstructing their input. In: IEEE; 2013:37-46. doi:10.1109/ISVD.2013.11'
apa: 'Biedl, T., Held, M., & Huber, S. (2013). Recognizing straight skeletons
and Voronoi diagrams and reconstructing their input (pp. 37–46). Presented at
the ISVD: Voronoi Diagrams in Science and Engineering, St. Petersburg, Russia:
IEEE. https://doi.org/10.1109/ISVD.2013.11'
chicago: Biedl, Therese, Martin Held, and Stefan Huber. “Recognizing Straight Skeletons
and Voronoi Diagrams and Reconstructing Their Input,” 37–46. IEEE, 2013. https://doi.org/10.1109/ISVD.2013.11.
ieee: 'T. Biedl, M. Held, and S. Huber, “Recognizing straight skeletons and Voronoi
diagrams and reconstructing their input,” presented at the ISVD: Voronoi Diagrams
in Science and Engineering, St. Petersburg, Russia, 2013, pp. 37–46.'
ista: 'Biedl T, Held M, Huber S. 2013. Recognizing straight skeletons and Voronoi
diagrams and reconstructing their input. ISVD: Voronoi Diagrams in Science and
Engineering, 2013 10th International Symposium on Voronoi Diagrams in Science
and Engineering (ISVD 2013) , , 37–46.'
mla: Biedl, Therese, et al. *Recognizing Straight Skeletons and Voronoi Diagrams
and Reconstructing Their Input*. IEEE, 2013, pp. 37–46, doi:10.1109/ISVD.2013.11.
short: T. Biedl, M. Held, S. Huber, in:, IEEE, 2013, pp. 37–46.
conference:
end_date: 2013-07-10
location: St. Petersburg, Russia
name: 'ISVD: Voronoi Diagrams in Science and Engineering'
start_date: 2013-07-08
date_created: 2018-12-11T11:56:20Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2021-01-12T06:56:00Z
day: '01'
department:
- _id: HeEd
doi: 10.1109/ISVD.2013.11
language:
- iso: eng
month: '12'
oa_version: None
page: 37 - 46
publication_identifier:
eisbn:
- '978-0-7695-5037-4 '
publication_status: published
publisher: IEEE
publist_id: '4763'
quality_controlled: '1'
scopus_import: 1
status: public
title: Recognizing straight skeletons and Voronoi diagrams and reconstructing their
input
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2210'
abstract:
- lang: eng
text: 'A straight skeleton is a well-known geometric structure, and several algorithms
exist to construct the straight skeleton for a given polygon. In this paper, we
ask the reverse question: Given the straight skeleton (in form of a tree with
a drawing in the plane, but with the exact position of the leaves unspecified),
can we reconstruct the polygon? We show that in most cases there exists at most
one polygon; in the remaining case there is an infinite number of polygons determined
by one angle that can range in an interval. We can find this (set of) polygon(s)
in linear time in the Real RAM computer model.'
author:
- first_name: Therese
full_name: Biedl, Therese
last_name: Biedl
- first_name: Martin
full_name: Held, Martin
last_name: Held
- first_name: Stefan
full_name: Huber, Stefan
id: 4700A070-F248-11E8-B48F-1D18A9856A87
last_name: Huber
orcid: 0000-0002-8871-5814
citation:
ama: 'Biedl T, Held M, Huber S. Reconstructing polygons from embedded straight skeletons.
In: *29th European Workshop on Computational Geometry*. TU Braunschweig;
2013:95-98.'
apa: 'Biedl, T., Held, M., & Huber, S. (2013). Reconstructing polygons from
embedded straight skeletons. In *29th European Workshop on Computational Geometry*
(pp. 95–98). Braunschweig, Germany: TU Braunschweig.'
chicago: Biedl, Therese, Martin Held, and Stefan Huber. “Reconstructing Polygons
from Embedded Straight Skeletons.” In *29th European Workshop on Computational
Geometry*, 95–98. TU Braunschweig, 2013.
ieee: T. Biedl, M. Held, and S. Huber, “Reconstructing polygons from embedded straight
skeletons,” in *29th European Workshop on Computational Geometry*, Braunschweig,
Germany, 2013, pp. 95–98.
ista: 'Biedl T, Held M, Huber S. 2013. Reconstructing polygons from embedded straight
skeletons. 29th European Workshop on Computational Geometry. EuroCG: European
Workshop on Computational Geometry, 95–98.'
mla: Biedl, Therese, et al. “Reconstructing Polygons from Embedded Straight Skeletons.”
*29th European Workshop on Computational Geometry*, TU Braunschweig, 2013,
pp. 95–98.
short: T. Biedl, M. Held, S. Huber, in:, 29th European Workshop on Computational
Geometry, TU Braunschweig, 2013, pp. 95–98.
conference:
end_date: 2013-03-20
location: Braunschweig, Germany
name: 'EuroCG: European Workshop on Computational Geometry'
start_date: 2013-03-17
date_created: 2018-12-11T11:56:21Z
date_published: 2013-03-01T00:00:00Z
date_updated: 2021-01-12T06:56:00Z
day: '01'
department:
- _id: HeEd
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ibr.cs.tu-bs.de/alg/eurocg13/booklet_eurocg13.pdf
month: '03'
oa: 1
oa_version: Submitted Version
page: 95 - 98
publication: 29th European Workshop on Computational Geometry
publication_status: published
publisher: TU Braunschweig
publist_id: '4762'
status: public
title: Reconstructing polygons from embedded straight skeletons
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...