---
_id: '2107'
abstract:
- lang: eng
text: We present a method for fabrication-oriented design of actuated deformable
characters that allows a user to automatically create physical replicas of digitally
designed characters using rapid manufacturing technologies. Given a deformable
character and a set of target poses as input, our method computes a small set
of actuators along with their locations on the surface and optimizes the internal
material distribution such that the resulting character exhibits the desired deformation
behavior. We approach this problem with a dedicated algorithm that combines finite-element
analysis, sparse regularization, and constrained optimization. We validate our
pipeline on a set of two- and three-dimensional example characters and present
results in simulation and physically-fabricated prototypes.
acknowledgement: This work was partly funded by the NCCR Co-Me of the Swiss NSF
author:
- first_name: Mélina
full_name: Skouras, Mélina
last_name: Skouras
- first_name: Bernhard
full_name: Thomaszewski, Bernhard
last_name: Thomaszewski
- first_name: Stelian
full_name: Coros, Stelian
last_name: Coros
- first_name: Bernd
full_name: Bernd Bickel
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
- first_name: Markus
full_name: Groß, Markus S
last_name: Groß
citation:
ama: Skouras M, Thomaszewski B, Coros S, Bickel B, Groß M. Computational design
of actuated deformable characters. ACM Transactions on Graphics. 2013;32(4).
doi:10.1145/2461912.2461979
apa: Skouras, M., Thomaszewski, B., Coros, S., Bickel, B., & Groß, M. (2013).
Computational design of actuated deformable characters. ACM Transactions on
Graphics. ACM. https://doi.org/10.1145/2461912.2461979
chicago: Skouras, Mélina, Bernhard Thomaszewski, Stelian Coros, Bernd Bickel, and
Markus Groß. “Computational Design of Actuated Deformable Characters.” ACM
Transactions on Graphics. ACM, 2013. https://doi.org/10.1145/2461912.2461979.
ieee: M. Skouras, B. Thomaszewski, S. Coros, B. Bickel, and M. Groß, “Computational
design of actuated deformable characters,” ACM Transactions on Graphics,
vol. 32, no. 4. ACM, 2013.
ista: Skouras M, Thomaszewski B, Coros S, Bickel B, Groß M. 2013. Computational
design of actuated deformable characters. ACM Transactions on Graphics. 32(4).
mla: Skouras, Mélina, et al. “Computational Design of Actuated Deformable Characters.”
ACM Transactions on Graphics, vol. 32, no. 4, ACM, 2013, doi:10.1145/2461912.2461979.
short: M. Skouras, B. Thomaszewski, S. Coros, B. Bickel, M. Groß, ACM Transactions
on Graphics 32 (2013).
date_created: 2018-12-11T11:55:45Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2021-01-12T06:55:21Z
day: '01'
doi: 10.1145/2461912.2461979
extern: 1
intvolume: ' 32'
issue: '4'
month: '07'
publication: ACM Transactions on Graphics
publication_status: published
publisher: ACM
publist_id: '4926'
quality_controlled: 0
status: public
title: Computational design of actuated deformable characters
type: journal_article
volume: 32
year: '2013'
...
---
_id: '2112'
abstract:
- lang: eng
text: Force-deformation measurements of cloth exhibit significant hysteresis, and
many researchers have identified internal friction as the source of this effect.
However, it has not been incorporated into computer animation models of cloth.
In this paper, we propose a model of internal friction based on an augmented reparameterization
of Dahl's model, and we show that this model provides a good match to several
important features of cloth hysteresis even with a minimal set of parameters.
We also propose novel parameter estimation procedures that are based on simple
and inexpensive setups and need only sparse data, as opposed to the complex hardware
and dense data acquisition of previous methods. Finally, we provide an algorithm
for the efficient simulation of internal friction, and we demonstrate it on simulation
examples that show disparate behavior with and without internal friction.
acknowledgement: This work was supported in part by the European Research Council
(ERC-2011-StG-280135 Animetrics) and the Spanish Ministry of Economy (TIN2012-35840).
author:
- first_name: Eder
full_name: Miguel, Eder
last_name: Miguel
- first_name: Rasmus
full_name: Tamstorf, Rasmus
last_name: Tamstorf
- first_name: Derek
full_name: Bradley, Derek J
last_name: Bradley
- first_name: Sara
full_name: Schvartzman, Sara C
last_name: Schvartzman
- first_name: Bernhard
full_name: Thomaszewski, Bernhard
last_name: Thomaszewski
- first_name: Bernd
full_name: Bernd Bickel
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
- first_name: Wojciech
full_name: Matusik, Wojciech
last_name: Matusik
- first_name: Steve
full_name: Marschner, Steve
last_name: Marschner
- first_name: Miguel
full_name: Otaduy, Miguel A
last_name: Otaduy
citation:
ama: Miguel E, Tamstorf R, Bradley D, et al. Modeling and estimation of internal
friction in cloth. ACM Transactions on Graphics. 2013;32(6). doi:10.1145/2508363.2508389
apa: Miguel, E., Tamstorf, R., Bradley, D., Schvartzman, S., Thomaszewski, B., Bickel,
B., … Otaduy, M. (2013). Modeling and estimation of internal friction in cloth.
ACM Transactions on Graphics. ACM. https://doi.org/10.1145/2508363.2508389
chicago: Miguel, Eder, Rasmus Tamstorf, Derek Bradley, Sara Schvartzman, Bernhard
Thomaszewski, Bernd Bickel, Wojciech Matusik, Steve Marschner, and Miguel Otaduy.
“Modeling and Estimation of Internal Friction in Cloth.” ACM Transactions on
Graphics. ACM, 2013. https://doi.org/10.1145/2508363.2508389
.
ieee: E. Miguel et al., “Modeling and estimation of internal friction in
cloth,” ACM Transactions on Graphics, vol. 32, no. 6. ACM, 2013.
ista: Miguel E, Tamstorf R, Bradley D, Schvartzman S, Thomaszewski B, Bickel B,
Matusik W, Marschner S, Otaduy M. 2013. Modeling and estimation of internal friction
in cloth. ACM Transactions on Graphics. 32(6).
mla: Miguel, Eder, et al. “Modeling and Estimation of Internal Friction in Cloth.”
ACM Transactions on Graphics, vol. 32, no. 6, ACM, 2013, doi:10.1145/2508363.2508389 .
short: E. Miguel, R. Tamstorf, D. Bradley, S. Schvartzman, B. Thomaszewski, B. Bickel,
W. Matusik, S. Marschner, M. Otaduy, ACM Transactions on Graphics 32 (2013).
date_created: 2018-12-11T11:55:47Z
date_published: 2013-11-01T00:00:00Z
date_updated: 2021-01-12T06:55:23Z
day: '01'
doi: '10.1145/2508363.2508389 '
extern: 1
intvolume: ' 32'
issue: '6'
month: '11'
publication: ACM Transactions on Graphics
publication_status: published
publisher: ACM
publist_id: '4923'
quality_controlled: 0
status: public
title: Modeling and estimation of internal friction in cloth
type: journal_article
volume: 32
year: '2013'
...
---
_id: '2117'
abstract:
- lang: eng
text: We prove new upper and lower bounds for Banach space-valued stochastic integrals
with respect to a compensated Poisson random measure. Our estimates apply to Banach
spaces with non-trivial martingale (co)type and extend various results in the
literature. We also develop a Malliavin framework to interpret Poisson stochastic
integrals as vector-valued Skorohod integrals, and prove a Clark-Ocone representation
formula.
acknowledgement: The first and third named authors were supported by VICI subsidy
639.033.604 of the Netherlands Organisation for Scientific Research (NWO). The first
and second named authors were supported by the German Research Foundation in the
Collaborative Research C
author:
- first_name: Sjoerd
full_name: Dirksen, Sjoerd
last_name: Dirksen
- first_name: Jan
full_name: Jan Maas
id: 4C5696CE-F248-11E8-B48F-1D18A9856A87
last_name: Maas
orcid: 0000-0002-0845-1338
- first_name: Jan
full_name: van Neerven, Jan M
last_name: Van Neerven
citation:
ama: Dirksen S, Maas J, Van Neerven J. Poisson stochastic integration in Banach
spaces. Electronic Journal of Probability. 2013;18. doi:10.1214/EJP.v18-2945
apa: Dirksen, S., Maas, J., & Van Neerven, J. (2013). Poisson stochastic integration
in Banach spaces. Electronic Journal of Probability. Institute of Mathematical
Statistics. https://doi.org/10.1214/EJP.v18-2945
chicago: Dirksen, Sjoerd, Jan Maas, and Jan Van Neerven. “Poisson Stochastic Integration
in Banach Spaces.” Electronic Journal of Probability. Institute of Mathematical
Statistics, 2013. https://doi.org/10.1214/EJP.v18-2945
.
ieee: S. Dirksen, J. Maas, and J. Van Neerven, “Poisson stochastic integration in
Banach spaces,” Electronic Journal of Probability, vol. 18. Institute of
Mathematical Statistics, 2013.
ista: Dirksen S, Maas J, Van Neerven J. 2013. Poisson stochastic integration in
Banach spaces. Electronic Journal of Probability. 18.
mla: Dirksen, Sjoerd, et al. “Poisson Stochastic Integration in Banach Spaces.”
Electronic Journal of Probability, vol. 18, Institute of Mathematical Statistics,
2013, doi:10.1214/EJP.v18-2945
.
short: S. Dirksen, J. Maas, J. Van Neerven, Electronic Journal of Probability 18
(2013).
date_created: 2018-12-11T11:55:49Z
date_published: 2013-11-18T00:00:00Z
date_updated: 2021-01-12T06:55:24Z
day: '18'
doi: '10.1214/EJP.v18-2945 '
extern: 1
intvolume: ' 18'
main_file_link:
- open_access: '1'
url: 'http://arxiv.org/abs/1307.7901 '
month: '11'
oa: 1
publication: Electronic Journal of Probability
publication_status: published
publisher: Institute of Mathematical Statistics
publist_id: '4917'
quality_controlled: 0
status: public
title: Poisson stochastic integration in Banach spaces
type: journal_article
volume: 18
year: '2013'
...
---
_id: '2113'
abstract:
- lang: eng
text: A new method fabricates custom surface reflectance and spatially varying bidirectional
reflectance distribution functions (svBRDFs). Researchers optimize a microgeometry
for a range of normal distribution functions and simulate the resulting surface's
effective reflectance. Using the simulation's results, they reproduce an input
svBRDF's appearance by distributing the microgeometry on the printed material's
surface. This method lets people print svBRDFs on planar samples with current
3D printing technology, even with a limited set of printing materials. It extends
naturally to printing svBRDFs on arbitrary shapes.
author:
- first_name: Olivier
full_name: Rouiller, Olivier
last_name: Rouiller
- first_name: Bernd
full_name: Bernd Bickel
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
- first_name: Jan
full_name: Kautz, Jan
last_name: Kautz
- first_name: Wojciech
full_name: Matusik, Wojciech
last_name: Matusik
- first_name: Marc
full_name: Alexa, Marc
last_name: Alexa
citation:
ama: Rouiller O, Bickel B, Kautz J, Matusik W, Alexa M. 3D printing spatially varying
BRDFs. IEEE Computer Graphics and Applications. 2013;33(6):48-57. doi:10.1109/MCG.2013.82
apa: Rouiller, O., Bickel, B., Kautz, J., Matusik, W., & Alexa, M. (2013). 3D
printing spatially varying BRDFs. IEEE Computer Graphics and Applications.
IEEE. https://doi.org/10.1109/MCG.2013.82
chicago: Rouiller, Olivier, Bernd Bickel, Jan Kautz, Wojciech Matusik, and Marc
Alexa. “3D Printing Spatially Varying BRDFs.” IEEE Computer Graphics and Applications.
IEEE, 2013. https://doi.org/10.1109/MCG.2013.82
.
ieee: O. Rouiller, B. Bickel, J. Kautz, W. Matusik, and M. Alexa, “3D printing spatially
varying BRDFs,” IEEE Computer Graphics and Applications, vol. 33, no. 6.
IEEE, pp. 48–57, 2013.
ista: Rouiller O, Bickel B, Kautz J, Matusik W, Alexa M. 2013. 3D printing spatially
varying BRDFs. IEEE Computer Graphics and Applications. 33(6), 48–57.
mla: Rouiller, Olivier, et al. “3D Printing Spatially Varying BRDFs.” IEEE Computer
Graphics and Applications, vol. 33, no. 6, IEEE, 2013, pp. 48–57, doi:10.1109/MCG.2013.82 .
short: O. Rouiller, B. Bickel, J. Kautz, W. Matusik, M. Alexa, IEEE Computer Graphics
and Applications 33 (2013) 48–57.
date_created: 2018-12-11T11:55:47Z
date_published: 2013-09-23T00:00:00Z
date_updated: 2021-01-12T06:55:23Z
day: '23'
doi: '10.1109/MCG.2013.82 '
extern: 1
intvolume: ' 33'
issue: '6'
month: '09'
page: 48 - 57
publication: IEEE Computer Graphics and Applications
publication_status: published
publisher: IEEE
publist_id: '4920'
quality_controlled: 0
status: public
title: 3D printing spatially varying BRDFs
type: journal_article
volume: 33
year: '2013'
...
---
_id: '2114'
abstract:
- lang: eng
text: 3D printing is considered a disruptive technology with a potentially tremendous
socioeconomic impact. The three articles in this special issue illustrate how
novel computer graphics approaches are advancing such digital fabrication.
author:
- first_name: Bernd
full_name: Bernd Bickel
id: 49876194-F248-11E8-B48F-1D18A9856A87
last_name: Bickel
orcid: 0000-0001-6511-9385
- first_name: Marc
full_name: Alexa, Marc
last_name: Alexa
citation:
ama: 'Bickel B, Alexa M. Computational aspects of fabrication: Modeling, design
and 3d printing. IEEE Computer Graphics and Applications. 2013;33(6):24-25.
doi:10.1109/MCG.2013.89'
apa: 'Bickel, B., & Alexa, M. (2013). Computational aspects of fabrication:
Modeling, design and 3d printing. IEEE Computer Graphics and Applications.
IEEE. https://doi.org/10.1109/MCG.2013.89'
chicago: 'Bickel, Bernd, and Marc Alexa. “Computational Aspects of Fabrication:
Modeling, Design and 3d Printing.” IEEE Computer Graphics and Applications.
IEEE, 2013. https://doi.org/10.1109/MCG.2013.89.'
ieee: 'B. Bickel and M. Alexa, “Computational aspects of fabrication: Modeling,
design and 3d printing,” IEEE Computer Graphics and Applications, vol.
33, no. 6. IEEE, pp. 24–25, 2013.'
ista: 'Bickel B, Alexa M. 2013. Computational aspects of fabrication: Modeling,
design and 3d printing. IEEE Computer Graphics and Applications. 33(6), 24–25.'
mla: 'Bickel, Bernd, and Marc Alexa. “Computational Aspects of Fabrication: Modeling,
Design and 3d Printing.” IEEE Computer Graphics and Applications, vol.
33, no. 6, IEEE, 2013, pp. 24–25, doi:10.1109/MCG.2013.89.'
short: B. Bickel, M. Alexa, IEEE Computer Graphics and Applications 33 (2013) 24–25.
date_created: 2018-12-11T11:55:48Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2021-01-12T06:55:24Z
day: '01'
doi: 10.1109/MCG.2013.89
extern: 1
intvolume: ' 33'
issue: '6'
month: '12'
page: 24 - 25
publication: IEEE Computer Graphics and Applications
publication_status: published
publisher: IEEE
publist_id: '4921'
quality_controlled: 0
status: public
title: 'Computational aspects of fabrication: Modeling, design and 3d printing'
type: journal_article
volume: 33
year: '2013'
...
---
_id: '2129'
abstract:
- lang: eng
text: "This paper continues the investigation of `Wasserstein-like' transportation
distances for probability measures on discrete sets. We prove that the discrete
transportation metrics on the d-dimensional discrete torus with mesh size 1/N
converge, when N→∞, to the standard 2-Wasserstein distance W_2 on the continuous
torus in the sense of Gromov-Hausdorff. This is the first convergence result for
the recently developed discrete transportation metrics. The result shows the compatibility
between these metrics and the well-established 2-Wasserstein metric. \n\n\n"
acknowledgement: JM acknowledges support by Rubicon subsidy 680-50-0901 of the Netherlands
Organisation for Scientific Research (NWO).
author:
- first_name: Nicola
full_name: Gigli, Nicola
last_name: Gigli
- first_name: Jan
full_name: Jan Maas
id: 4C5696CE-F248-11E8-B48F-1D18A9856A87
last_name: Maas
orcid: 0000-0002-0845-1338
citation:
ama: Gigli N, Maas J. Gromov-Hausdorff convergence of discrete transportation metrics.
SIAM Journal on Mathematical Analysis. 2013;45(2):879-899. doi:10.1137/120886315
apa: Gigli, N., & Maas, J. (2013). Gromov-Hausdorff convergence of discrete
transportation metrics. SIAM Journal on Mathematical Analysis. Society
for Industrial and Applied Mathematics . https://doi.org/10.1137/120886315
chicago: Gigli, Nicola, and Jan Maas. “Gromov-Hausdorff Convergence of Discrete
Transportation Metrics.” SIAM Journal on Mathematical Analysis. Society
for Industrial and Applied Mathematics , 2013. https://doi.org/10.1137/120886315 .
ieee: N. Gigli and J. Maas, “Gromov-Hausdorff convergence of discrete transportation
metrics,” SIAM Journal on Mathematical Analysis, vol. 45, no. 2. Society
for Industrial and Applied Mathematics , pp. 879–899, 2013.
ista: Gigli N, Maas J. 2013. Gromov-Hausdorff convergence of discrete transportation
metrics. SIAM Journal on Mathematical Analysis. 45(2), 879–899.
mla: Gigli, Nicola, and Jan Maas. “Gromov-Hausdorff Convergence of Discrete Transportation
Metrics.” SIAM Journal on Mathematical Analysis, vol. 45, no. 2, Society
for Industrial and Applied Mathematics , 2013, pp. 879–99, doi:10.1137/120886315 .
short: N. Gigli, J. Maas, SIAM Journal on Mathematical Analysis 45 (2013) 879–899.
date_created: 2018-12-11T11:55:53Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T06:55:29Z
day: '01'
doi: '10.1137/120886315 '
extern: 1
intvolume: ' 45'
issue: '2'
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1207.6501
month: '01'
oa: 1
page: 879 - 899
publication: SIAM Journal on Mathematical Analysis
publication_status: published
publisher: 'Society for Industrial and Applied Mathematics '
publist_id: '4904'
quality_controlled: 0
status: public
title: Gromov-Hausdorff convergence of discrete transportation metrics
type: journal_article
volume: 45
year: '2013'
...
---
_id: '2139'
abstract:
- lang: eng
text: Recently it has been shown that pairs of atoms can form metastable bonds due
to non-conservative forces induced by dissipation [Lemeshko&Weimer, Nature
Comm. 4, 2230 (2013)]. Here we study the dynamics of interaction-induced coherent
population trapping - the process responsible for the formation of dissipatively
bound molecules. We derive the effective dissipative potentials induced between
ultracold atoms by laser light, and study the time evolution of the scattering
states. We demonstrate that binding occurs on short timescales of ~10 microseconds,
even if the initial kinetic energy of the atoms significantly exceeds the depth
of the dissipative potential. Dissipatively-bound molecules with preordained bond
lengths and vibrational wavefunctions can be created and detected in current experiments
with ultracold atoms.
acknowledgement: The work was supported by the NSF through a grant for the Institute
for Theoretical Atomic, Molecular, and Optical Physics at Harvard University and
Smithsonian Astrophysical Observatory
author:
- first_name: Mikhail
full_name: Mikhail Lemeshko
id: 37CB05FA-F248-11E8-B48F-1D18A9856A87
last_name: Lemeshko
orcid: 0000-0002-6990-7802
citation:
ama: Lemeshko M. Manipulating scattering of ultracold atoms with light-induced dissipation.
Frontiers Physics. 2013;1(17). doi:10.3389/fphy.2013.00017
apa: Lemeshko, M. (2013). Manipulating scattering of ultracold atoms with light-induced
dissipation. Frontiers Physics. Frontiers Media. https://doi.org/10.3389/fphy.2013.00017
chicago: Lemeshko, Mikhail. “Manipulating Scattering of Ultracold Atoms with Light-Induced
Dissipation.” Frontiers Physics. Frontiers Media, 2013. https://doi.org/10.3389/fphy.2013.00017.
ieee: M. Lemeshko, “Manipulating scattering of ultracold atoms with light-induced
dissipation,” Frontiers Physics, vol. 1, no. 17. Frontiers Media, 2013.
ista: Lemeshko M. 2013. Manipulating scattering of ultracold atoms with light-induced
dissipation. Frontiers Physics. 1(17).
mla: Lemeshko, Mikhail. “Manipulating Scattering of Ultracold Atoms with Light-Induced
Dissipation.” Frontiers Physics, vol. 1, no. 17, Frontiers Media, 2013,
doi:10.3389/fphy.2013.00017.
short: M. Lemeshko, Frontiers Physics 1 (2013).
date_created: 2018-12-11T11:55:56Z
date_published: 2013-10-07T00:00:00Z
date_updated: 2021-01-12T06:55:32Z
day: '07'
doi: 10.3389/fphy.2013.00017
extern: 1
intvolume: ' 1'
issue: '17'
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1307.8129
month: '10'
oa: 1
publication: Frontiers Physics
publication_status: published
publisher: Frontiers Media
publist_id: '4885'
quality_controlled: 0
status: public
title: Manipulating scattering of ultracold atoms with light-induced dissipation
type: journal_article
volume: 1
year: '2013'
...
---
_id: '2181'
abstract:
- lang: eng
text: 'There is a trade-off between performance and correctness in implementing
concurrent data structures. Better performance may be achieved at the expense
of relaxing correctness, by redefining the semantics of data structures. We address
such a redefinition of data structure semantics and present a systematic and formal
framework for obtaining new data structures by quantitatively relaxing existing
ones. We view a data structure as a sequential specification S containing all
"legal" sequences over an alphabet of method calls. Relaxing the data
structure corresponds to defining a distance from any sequence over the alphabet
to the sequential specification: the k-relaxed sequential specification contains
all sequences over the alphabet within distance k from the original specification.
In contrast to other existing work, our relaxations are semantic (distance in
terms of data structure states). As an instantiation of our framework, we present
two simple yet generic relaxation schemes, called out-of-order and stuttering
relaxation, along with several ways of computing distances. We show that the out-of-order
relaxation, when further instantiated to stacks, queues, and priority queues,
amounts to tolerating bounded out-of-order behavior, which cannot be captured
by a purely syntactic relaxation (distance in terms of sequence manipulation,
e.g. edit distance). We give concurrent implementations of relaxed data structures
and demonstrate that bounded relaxations provide the means for trading correctness
for performance in a controlled way. The relaxations are monotonic which further
highlights the trade-off: increasing k increases the number of permitted sequences,
which as we demonstrate can lead to better performance. Finally, since a relaxed
stack or queue also implements a pool, we actually have new concurrent pool implementations
that outperform the state-of-the-art ones.'
acknowledgement: ' and an Elise Richter Fellowship (Austrian Science Fund V00125). '
author:
- 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: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
- first_name: Hannes
full_name: Payer, Hannes
last_name: Payer
- first_name: Ali
full_name: Sezgin, Ali
id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
last_name: Sezgin
- first_name: Ana
full_name: Sokolova, Ana
last_name: Sokolova
citation:
ama: 'Henzinger TA, Kirsch C, Payer H, Sezgin A, Sokolova A. Quantitative relaxation
of concurrent data structures. In: Proceedings of the 40th Annual ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Language. ACM; 2013:317-328. doi:10.1145/2429069.2429109'
apa: 'Henzinger, T. A., Kirsch, C., Payer, H., Sezgin, A., & Sokolova, A. (2013).
Quantitative relaxation of concurrent data structures. In Proceedings of the
40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming language
(pp. 317–328). Rome, Italy: ACM. https://doi.org/10.1145/2429069.2429109'
chicago: Henzinger, Thomas A, Christoph Kirsch, Hannes Payer, Ali Sezgin, and Ana
Sokolova. “Quantitative Relaxation of Concurrent Data Structures.” In Proceedings
of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Language,
317–28. ACM, 2013. https://doi.org/10.1145/2429069.2429109.
ieee: T. A. Henzinger, C. Kirsch, H. Payer, A. Sezgin, and A. Sokolova, “Quantitative
relaxation of concurrent data structures,” in Proceedings of the 40th annual
ACM SIGPLAN-SIGACT symposium on Principles of programming language, Rome,
Italy, 2013, pp. 317–328.
ista: 'Henzinger TA, Kirsch C, Payer H, Sezgin A, Sokolova A. 2013. Quantitative
relaxation of concurrent data structures. Proceedings of the 40th annual ACM SIGPLAN-SIGACT
symposium on Principles of programming language. POPL: Principles of Programming
Languages, 317–328.'
mla: Henzinger, Thomas A., et al. “Quantitative Relaxation of Concurrent Data Structures.”
Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of
Programming Language, ACM, 2013, pp. 317–28, doi:10.1145/2429069.2429109.
short: T.A. Henzinger, C. Kirsch, H. Payer, A. Sezgin, A. Sokolova, in:, Proceedings
of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Language,
ACM, 2013, pp. 317–328.
conference:
end_date: 2013-01-25
location: Rome, Italy
name: 'POPL: Principles of Programming Languages'
start_date: 2013-01-23
date_created: 2018-12-11T11:56:11Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2023-02-21T16:06:49Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.1145/2429069.2429109
ec_funded: 1
file:
- access_level: open_access
checksum: adf465e70948f4e80e48057524516456
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:33Z
date_updated: 2020-07-14T12:45:31Z
file_id: '5086'
file_name: IST-2014-198-v1+1_popl128-henzinger-clean.pdf
file_size: 294689
relation: main_file
file_date_updated: 2020-07-14T12:45:31Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 317 - 328
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles
of programming language
publication_identifier:
isbn:
- 978-1-4503-1832-7
publication_status: published
publisher: ACM
publist_id: '4801'
pubrep_id: '198'
quality_controlled: '1'
related_material:
record:
- id: '10901'
relation: later_version
status: deleted
scopus_import: 1
status: public
title: Quantitative relaxation of concurrent data structures
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2182'
abstract:
- lang: eng
text: We propose a general framework for abstraction with respect to quantitative
properties, such as worst-case execution time, or power consumption. Our framework
provides a systematic way for counter-example guided abstraction refinement for
quantitative properties. The salient aspect of the framework is that it allows
anytime verification, that is, verification algorithms that can be stopped at
any time (for example, due to exhaustion of memory), and report approximations
that improve monotonically when the algorithms are given more time. We instantiate
the framework with a number of quantitative abstractions and refinement schemes,
which differ in terms of how much quantitative information they keep from the
original system. We introduce both state-based and trace-based quantitative abstractions,
and we describe conditions that define classes of quantitative properties for
which the abstractions provide over-approximations. We give algorithms for evaluating
the quantitative properties on the abstract systems. We present algorithms for
counter-example based refinements for quantitative properties for both state-based
and segment-based abstractions. We perform a case study on worst-case execution
time of executables to evaluate the anytime verification aspect and the quantitative
abstractions we proposed.
author:
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
- 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: Arjun
full_name: Radhakrishna, Arjun
id: 3B51CAC4-F248-11E8-B48F-1D18A9856A87
last_name: Radhakrishna
citation:
ama: 'Cerny P, Henzinger TA, Radhakrishna A. Quantitative abstraction refinement.
In: Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles
of Programming Language. ACM; 2013:115-128. doi:10.1145/2429069.2429085'
apa: 'Cerny, P., Henzinger, T. A., & Radhakrishna, A. (2013). Quantitative abstraction
refinement. In Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium
on Principles of programming language (pp. 115–128). Rome, Italy: ACM. https://doi.org/10.1145/2429069.2429085'
chicago: Cerny, Pavol, Thomas A Henzinger, and Arjun Radhakrishna. “Quantitative
Abstraction Refinement.” In Proceedings of the 40th Annual ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Language, 115–28. ACM, 2013. https://doi.org/10.1145/2429069.2429085.
ieee: P. Cerny, T. A. Henzinger, and A. Radhakrishna, “Quantitative abstraction
refinement,” in Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium
on Principles of programming language, Rome, Italy, 2013, pp. 115–128.
ista: 'Cerny P, Henzinger TA, Radhakrishna A. 2013. Quantitative abstraction refinement.
Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming
language. POPL: Principles of Programming Languages, 115–128.'
mla: Cerny, Pavol, et al. “Quantitative Abstraction Refinement.” Proceedings
of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Language,
ACM, 2013, pp. 115–28, doi:10.1145/2429069.2429085.
short: P. Cerny, T.A. Henzinger, A. Radhakrishna, in:, Proceedings of the 40th Annual
ACM SIGPLAN-SIGACT Symposium on Principles of Programming Language, ACM, 2013,
pp. 115–128.
conference:
end_date: 2013-01-25
location: Rome, Italy
name: 'POPL: Principles of Programming Languages'
start_date: 2013-07-23
date_created: 2018-12-11T11:56:11Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T06:55:50Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/2429069.2429085
ec_funded: 1
language:
- iso: eng
month: '01'
oa_version: None
page: 115 - 128
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
publication: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles
of programming language
publication_status: published
publisher: ACM
publist_id: '4800'
quality_controlled: '1'
scopus_import: 1
status: public
title: Quantitative abstraction refinement
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
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'
...