---
_id: '14703'
abstract:
- lang: eng
text: We present a discretization of the dynamic optimal transport problem for which
we can obtain the convergence rate for the value of the transport cost to its
continuous value when the temporal and spatial stepsize vanish. This convergence
result does not require any regularity assumption on the measures, though experiments
suggest that the rate is not sharp. Via an analysis of the duality gap we also
obtain the convergence rates for the gradient of the optimal potentials and the
velocity field under mild regularity assumptions. To obtain such rates we discretize
the dual formulation of the dynamic optimal transport problem and use the mature
literature related to the error due to discretizing the Hamilton-Jacobi equation.
acknowledgement: "The authors would like to thank Chris Wojtan for his continuous
support and several interesting discussions. Part of this research was performed
during two visits: one of SI to the BIDSA research center at Bocconi University,
and one of HL to the Institute of Science and Technology Austria. Both host institutions
are warmly acknowledged for the hospital-\r\nity. HL is partially supported by the
MUR-Prin 2022-202244A7YL “Gradient Flows and Non-Smooth Geometric Structures with
Applications to Optimization and Machine Learning”, funded by the European Union
- Next Generation EU. SI is supported in part by ERC Consolidator Grant 101045083
“CoDiNA” funded by the European Research Council."
article_number: '2312.12213'
article_processing_charge: No
arxiv: 1
author:
- first_name: Sadashige
full_name: Ishida, Sadashige
id: 6F7C4B96-A8E9-11E9-A7CA-09ECE5697425
last_name: Ishida
- first_name: Hugo
full_name: Lavenant, Hugo
last_name: Lavenant
citation:
ama: Ishida S, Lavenant H. Quantitative convergence of a discretization of dynamic
optimal transport using the dual formulation. arXiv. doi:10.48550/arXiv.2312.12213
apa: Ishida, S., & Lavenant, H. (n.d.). Quantitative convergence of a discretization
of dynamic optimal transport using the dual formulation. arXiv. https://doi.org/10.48550/arXiv.2312.12213
chicago: Ishida, Sadashige, and Hugo Lavenant. “Quantitative Convergence of a Discretization
of Dynamic Optimal Transport Using the Dual Formulation.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2312.12213.
ieee: S. Ishida and H. Lavenant, “Quantitative convergence of a discretization of
dynamic optimal transport using the dual formulation,” arXiv. .
ista: Ishida S, Lavenant H. Quantitative convergence of a discretization of dynamic
optimal transport using the dual formulation. arXiv, 2312.12213.
mla: Ishida, Sadashige, and Hugo Lavenant. “Quantitative Convergence of a Discretization
of Dynamic Optimal Transport Using the Dual Formulation.” ArXiv, 2312.12213,
doi:10.48550/arXiv.2312.12213.
short: S. Ishida, H. Lavenant, ArXiv (n.d.).
date_created: 2023-12-21T10:14:37Z
date_published: 2023-12-19T00:00:00Z
date_updated: 2023-12-27T13:44:33Z
day: '19'
department:
- _id: GradSch
- _id: ChWo
doi: 10.48550/arXiv.2312.12213
external_id:
arxiv:
- '2312.12213'
keyword:
- Optimal transport
- Hamilton-Jacobi equation
- convex optimization
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2312.12213
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 34bc2376-11ca-11ed-8bc3-9a3b3961a088
grant_number: '101045083'
name: Computational Discovery of Numerical Algorithms for Animation and Simulation
of Natural Phenomena
publication: arXiv
publication_status: submitted
status: public
title: Quantitative convergence of a discretization of dynamic optimal transport using
the dual formulation
type: preprint
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '12984'
abstract:
- lang: eng
text: Tattoos are a highly popular medium, with both artistic and medical applications.
Although the mechanical process of tattoo application has evolved historically,
the results are reliant on the artisanal skill of the artist. This can be especially
challenging for some skin tones, or in cases where artists lack experience. We
provide the first systematic overview of tattooing as a computational fabrication
technique. We built an automated tattooing rig and a recipe for the creation of
silicone sheets mimicking realistic skin tones, which allowed us to create an
accurate model predicting tattoo appearance. This enables several exciting applications
including tattoo previewing, color retargeting, novel ink spectra optimization,
color-accurate prosthetics, and more.
acknowledged_ssus:
- _id: M-Shop
acknowledgement: We thank Todor Asenov and the Miba Machine Shop for their help in
assembling the tattoo machine and manufacturing the substrates. We thank Geysler
Rodrigues for the insightful discussions on tattooing practices from a professional
artist's perspective. We thank Maria Fernanda Portugal for sharing a doctor's perspective
on medical applications of tattoos. This work is graciously supported by the FWF
Lise Meitner (Grant M 3319).
article_number: '67'
article_processing_charge: No
article_type: original
author:
- first_name: Michael
full_name: Piovarci, Michael
id: 62E473F4-5C99-11EA-A40E-AF823DDC885E
last_name: Piovarci
orcid: 0000-0002-5062-4474
- first_name: Alexandre
full_name: Chapiro, Alexandre
last_name: Chapiro
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
citation:
ama: 'Piovarci M, Chapiro A, Bickel B. Skin-Screen: A computational fabrication
framework for color tattoos. Transactions on Graphics. 2023;42(4). doi:10.1145/3592432'
apa: 'Piovarci, M., Chapiro, A., & Bickel, B. (2023). Skin-Screen: A computational
fabrication framework for color tattoos. Transactions on Graphics. Los
Angeles, CA, United States: Association for Computing Machinery. https://doi.org/10.1145/3592432'
chicago: 'Piovarci, Michael, Alexandre Chapiro, and Bernd Bickel. “Skin-Screen:
A Computational Fabrication Framework for Color Tattoos.” Transactions on Graphics.
Association for Computing Machinery, 2023. https://doi.org/10.1145/3592432.'
ieee: 'M. Piovarci, A. Chapiro, and B. Bickel, “Skin-Screen: A computational fabrication
framework for color tattoos,” Transactions on Graphics, vol. 42, no. 4.
Association for Computing Machinery, 2023.'
ista: 'Piovarci M, Chapiro A, Bickel B. 2023. Skin-Screen: A computational fabrication
framework for color tattoos. Transactions on Graphics. 42(4), 67.'
mla: 'Piovarci, Michael, et al. “Skin-Screen: A Computational Fabrication Framework
for Color Tattoos.” Transactions on Graphics, vol. 42, no. 4, 67, Association
for Computing Machinery, 2023, doi:10.1145/3592432.'
short: M. Piovarci, A. Chapiro, B. Bickel, Transactions on Graphics 42 (2023).
conference:
end_date: 2023-08-10
location: Los Angeles, CA, United States
name: 'SIGGRAPH: Computer Graphics and Interactive Techniques Conference'
start_date: 2023-08-06
date_created: 2023-05-16T09:39:14Z
date_published: 2023-07-26T00:00:00Z
date_updated: 2024-01-29T10:27:23Z
day: '26'
ddc:
- '004'
department:
- _id: BeBi
doi: 10.1145/3592432
external_id:
isi:
- '001044671300033'
file:
- access_level: open_access
checksum: 5f0a6867689e025a661bd0b4fd90b821
content_type: application/pdf
creator: mpiovarc
date_created: 2023-05-16T09:38:25Z
date_updated: 2023-05-16T09:38:25Z
file_id: '12985'
file_name: Piovarci2023.pdf
file_size: 30817343
relation: main_file
success: 1
file_date_updated: 2023-05-16T09:38:25Z
has_accepted_license: '1'
intvolume: ' 42'
isi: 1
issue: '4'
keyword:
- appearance
- modeling
- reproduction
- tattoo
- skin color
- gamut mapping
- ink-optimization
- prosthetic
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
project:
- _id: eb901961-77a9-11ec-83b8-f5c883a62027
grant_number: M03319
name: Perception-Aware Appearance Fabrication
publication: Transactions on Graphics
publication_identifier:
eissn:
- 1557-7368
issn:
- 0730-0301
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: 'Skin-Screen: A computational fabrication framework for color tattoos'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 42
year: '2023'
...
---
_id: '9817'
abstract:
- lang: eng
text: Elastic bending of initially flat slender elements allows the realization
and economic fabrication of intriguing curved shapes. In this work, we derive
an intuitive but rigorous geometric characterization of the design space of plane
elastic rods with variable stiffness. It enables designers to determine which
shapes are physically viable with active bending by visual inspection alone. Building
on these insights, we propose a method for efficiently designing the geometry
of a flat elastic rod that realizes a target equilibrium curve, which only requires
solving a linear program. We implement this method in an interactive computational
design tool that gives feedback about the feasibility of a design, and computes
the geometry of the structural elements necessary to realize it within an instant.
The tool also offers an iterative optimization routine that improves the fabricability
of a model while modifying it as little as possible. In addition, we use our geometric
characterization to derive an algorithm for analyzing and recovering the stability
of elastic curves that would otherwise snap out of their unstable equilibrium
shapes by buckling. We show the efficacy of our approach by designing and manufacturing
several physical models that are assembled from flat elements.
acknowledgement: "We thank the anonymous reviewers for their generous feedback, and
Michal Piovarči for his help in producing the supplemental video. This project has
received funding from the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme (grant agreement No 715767).\r\n"
article_number: '126'
article_processing_charge: No
article_type: original
author:
- first_name: Christian
full_name: Hafner, Christian
id: 400429CC-F248-11E8-B48F-1D18A9856A87
last_name: Hafner
- first_name: Bernd
full_name: Bickel, Bernd
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
citation:
ama: Hafner C, Bickel B. The design space of plane elastic curves. ACM Transactions
on Graphics. 2021;40(4). doi:10.1145/3450626.3459800
apa: 'Hafner, C., & Bickel, B. (2021). The design space of plane elastic curves.
ACM Transactions on Graphics. Virtual: Association for Computing Machinery.
https://doi.org/10.1145/3450626.3459800'
chicago: Hafner, Christian, and Bernd Bickel. “The Design Space of Plane Elastic
Curves.” ACM Transactions on Graphics. Association for Computing Machinery,
2021. https://doi.org/10.1145/3450626.3459800.
ieee: C. Hafner and B. Bickel, “The design space of plane elastic curves,” ACM
Transactions on Graphics, vol. 40, no. 4. Association for Computing Machinery,
2021.
ista: Hafner C, Bickel B. 2021. The design space of plane elastic curves. ACM Transactions
on Graphics. 40(4), 126.
mla: Hafner, Christian, and Bernd Bickel. “The Design Space of Plane Elastic Curves.”
ACM Transactions on Graphics, vol. 40, no. 4, 126, Association for Computing
Machinery, 2021, doi:10.1145/3450626.3459800.
short: C. Hafner, B. Bickel, ACM Transactions on Graphics 40 (2021).
conference:
end_date: 2021-08-13
location: Virtual
name: 'SIGGRAF: Special Interest Group on Computer Graphics and Interactive Techniques'
start_date: 2021-08-09
date_created: 2021-08-08T22:01:26Z
date_published: 2021-07-19T00:00:00Z
date_updated: 2024-03-25T23:30:26Z
day: '19'
ddc:
- '516'
department:
- _id: BeBi
doi: 10.1145/3450626.3459800
ec_funded: 1
external_id:
isi:
- '000674930900091'
file:
- access_level: open_access
checksum: 7e5d08ce46b0451b3102eacd3d00f85f
content_type: application/pdf
creator: chafner
date_created: 2021-10-18T10:42:15Z
date_updated: 2021-10-18T10:42:15Z
file_id: '10150'
file_name: elastic-curves-paper.pdf
file_size: 17064290
relation: main_file
success: 1
- access_level: open_access
checksum: 0088643478be7c01a703b5b10767348f
content_type: application/pdf
creator: chafner
date_created: 2021-10-18T10:42:22Z
date_updated: 2021-10-18T10:42:22Z
file_id: '10151'
file_name: elastic-curves-supp.pdf
file_size: 547156
relation: supplementary_material
file_date_updated: 2021-10-18T10:42:22Z
has_accepted_license: '1'
intvolume: ' 40'
isi: 1
issue: '4'
keyword:
- Computing methodologies
- shape modeling
- modeling and simulation
- theory of computation
- computational geometry
- mathematics of computing
- mathematical optimization
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 24F9549A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '715767'
name: 'MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and
Modeling'
publication: ACM Transactions on Graphics
publication_identifier:
eissn:
- 1557-7368
issn:
- 0730-0301
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
link:
- description: News on IST Website
relation: press_release
url: https://ist.ac.at/en/news/designing-with-elastic-structures/
record:
- id: '12897'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: The design space of plane elastic curves
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 40
year: '2021'
...
---
_id: '7130'
abstract:
- lang: eng
text: "We show that statistical criticality, i.e. the occurrence of power law frequency
distributions, arises in samples that are maximally informative about the underlying
generating process. In order to reach this conclusion, we first identify the frequency
with which different outcomes occur in a sample, as the variable carrying useful
information on the generative process. The entropy of the frequency, that we call
relevance, provides an upper bound to the number of informative bits. This differs
from the entropy of the data, that we take as a measure of resolution. Samples
that maximise relevance at a given resolution—that we call maximally informative
samples—exhibit statistical criticality. In particular, Zipf's law arises at the
optimal trade-off between resolution (i.e. compression) and relevance. As a byproduct,
we derive a bound of the maximal number of parameters that can be estimated from
a dataset, in the absence of prior knowledge on the generative model.\r\n\r\nFurthermore,
we relate criticality to the statistical properties of the representation of the
data generating process. We show that, as a consequence of the concentration property
of the asymptotic equipartition property, representations that are maximally informative
about the data generating process are characterised by an exponential distribution
of energy levels. This arises from a principle of minimal entropy, that is conjugate
of the maximum entropy principle in statistical mechanics. This explains why statistical
criticality requires no parameter fine tuning in maximally informative samples."
acknowledgement: We acknowledge interesting discussions with M Abbott, E Aurell, J
Barbier, R Monasson, T Mora, I Nemenman, N Tishby and R Zecchina. This research
was supported by the Kavli Foundation and the Centre of Excellence scheme of the
Research Council of Norway (Centre for Neural Computation) (RJC and YR), by the
Basic Science Research Program through the National Research Foundation of Korea
(NRF), funded by the Ministry of Education (2016R1D1A1B03932264) (JJ), and, in part,
by the ICTP through the OEA-AC-98 (JS).
article_number: '063402'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Ryan J
full_name: Cubero, Ryan J
id: 850B2E12-9CD4-11E9-837F-E719E6697425
last_name: Cubero
orcid: 0000-0003-0002-1867
- first_name: Junghyo
full_name: Jo, Junghyo
last_name: Jo
- first_name: Matteo
full_name: Marsili, Matteo
last_name: Marsili
- first_name: Yasser
full_name: Roudi, Yasser
last_name: Roudi
- first_name: Juyong
full_name: Song, Juyong
last_name: Song
citation:
ama: 'Cubero RJ, Jo J, Marsili M, Roudi Y, Song J. Statistical criticality arises
in most informative representations. Journal of Statistical Mechanics: Theory
and Experiment. 2019;2019(6). doi:10.1088/1742-5468/ab16c8'
apa: 'Cubero, R. J., Jo, J., Marsili, M., Roudi, Y., & Song, J. (2019). Statistical
criticality arises in most informative representations. Journal of Statistical
Mechanics: Theory and Experiment. IOP Publishing. https://doi.org/10.1088/1742-5468/ab16c8'
chicago: 'Cubero, Ryan J, Junghyo Jo, Matteo Marsili, Yasser Roudi, and Juyong Song.
“Statistical Criticality Arises in Most Informative Representations.” Journal
of Statistical Mechanics: Theory and Experiment. IOP Publishing, 2019. https://doi.org/10.1088/1742-5468/ab16c8.'
ieee: 'R. J. Cubero, J. Jo, M. Marsili, Y. Roudi, and J. Song, “Statistical criticality
arises in most informative representations,” Journal of Statistical Mechanics:
Theory and Experiment, vol. 2019, no. 6. IOP Publishing, 2019.'
ista: 'Cubero RJ, Jo J, Marsili M, Roudi Y, Song J. 2019. Statistical criticality
arises in most informative representations. Journal of Statistical Mechanics:
Theory and Experiment. 2019(6), 063402.'
mla: 'Cubero, Ryan J., et al. “Statistical Criticality Arises in Most Informative
Representations.” Journal of Statistical Mechanics: Theory and Experiment,
vol. 2019, no. 6, 063402, IOP Publishing, 2019, doi:10.1088/1742-5468/ab16c8.'
short: 'R.J. Cubero, J. Jo, M. Marsili, Y. Roudi, J. Song, Journal of Statistical
Mechanics: Theory and Experiment 2019 (2019).'
date_created: 2019-11-26T22:36:09Z
date_published: 2019-06-17T00:00:00Z
date_updated: 2021-01-12T08:11:57Z
day: '17'
doi: 10.1088/1742-5468/ab16c8
extern: '1'
external_id:
arxiv:
- '1808.00249'
intvolume: ' 2019'
issue: '6'
keyword:
- optimization under uncertainty
- source coding
- large deviation
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1808.00249
month: '06'
oa: 1
oa_version: Preprint
publication: 'Journal of Statistical Mechanics: Theory and Experiment'
publication_identifier:
issn:
- 1742-5468
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
status: public
title: Statistical criticality arises in most informative representations
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2019
year: '2019'
...
---
_id: '11683'
abstract:
- lang: eng
text: The vertex connectivity κ of a graph is the smallest number of vertices whose
deletion separates the graph or makes it trivial. We present the fastest known
deterministic algorithm for finding the vertex connectivity and a corresponding
separator. The time for a digraph having n vertices and m edges is O(min{κ3 +
n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized
algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have
nonnegative weights the weighted vertex connectivity is found in time O(κ1nmlog(n2/m))
where κ1 ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n2/m))
with error probability 1/2. The main algorithm combines two previous vertex connectivity
algorithms and a generalization of the preflow-push algorithm of Hao and Orlin
(1994, J. Algorithms17, 424–446) that computes edge connectivity.
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Satish
full_name: Rao, Satish
last_name: Rao
- first_name: Harold N.
full_name: Gabow, Harold N.
last_name: Gabow
citation:
ama: 'Henzinger MH, Rao S, Gabow HN. Computing vertex connectivity: New bounds from
old techniques. Journal of Algorithms. 2000;34(2):222-250. doi:10.1006/jagm.1999.1055'
apa: 'Henzinger, M. H., Rao, S., & Gabow, H. N. (2000). Computing vertex connectivity:
New bounds from old techniques. Journal of Algorithms. Elsevier. https://doi.org/10.1006/jagm.1999.1055'
chicago: 'Henzinger, Monika H, Satish Rao, and Harold N. Gabow. “Computing Vertex
Connectivity: New Bounds from Old Techniques.” Journal of Algorithms. Elsevier,
2000. https://doi.org/10.1006/jagm.1999.1055.'
ieee: 'M. H. Henzinger, S. Rao, and H. N. Gabow, “Computing vertex connectivity:
New bounds from old techniques,” Journal of Algorithms, vol. 34, no. 2.
Elsevier, pp. 222–250, 2000.'
ista: 'Henzinger MH, Rao S, Gabow HN. 2000. Computing vertex connectivity: New bounds
from old techniques. Journal of Algorithms. 34(2), 222–250.'
mla: 'Henzinger, Monika H., et al. “Computing Vertex Connectivity: New Bounds from
Old Techniques.” Journal of Algorithms, vol. 34, no. 2, Elsevier, 2000,
pp. 222–50, doi:10.1006/jagm.1999.1055.'
short: M.H. Henzinger, S. Rao, H.N. Gabow, Journal of Algorithms 34 (2000) 222–250.
date_created: 2022-07-28T08:56:10Z
date_published: 2000-02-01T00:00:00Z
date_updated: 2022-09-12T09:06:48Z
day: '01'
doi: 10.1006/jagm.1999.1055
extern: '1'
intvolume: ' 34'
issue: '2'
keyword:
- Computational Theory and Mathematics
- Computational Mathematics
- Control and Optimization
language:
- iso: eng
month: '02'
oa_version: None
page: 222-250
publication: Journal of Algorithms
publication_identifier:
issn:
- 0196-6774
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Computing vertex connectivity: New bounds from old techniques'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2000'
...