3 Search Results for "Berger, Richard"

Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2023.62
Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading (Media Exposition)

Authors: Richard Berger, Vincent Ha, David Kratz, Michael Lin, Jeremy Moyer, and Christopher J. Tralie

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We provide a skit and an applet to illustrate fractional cascading in the context of half-plane range search for points in the Euclidean plane, which takes O(log N + h) output-sensitive time. In the video, a group of news anchors struggles to find the correct data structure to efficiently send out an early warning to the residents of Philadelphia who will be overtaken by a marching line of Godzillas. After exploring several options, the group eventually settles on onions and fractional cascading, only to discover that they themselves are in the line of fire! In the applet, we show step by step details of preprocessing to build the onions with fractional cascading and the subsequent query of the "Godzilla line" against the onion layers. Our video skit and applet can be found at https://ctralie.github.io/GodzillaOnions/
Cite as

Richard Berger, Vincent Ha, David Kratz, Michael Lin, Jeremy Moyer, and Christopher J. Tralie. Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 62:1-62:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:LIPIcs.SoCG.2023.62,
  author =	{Berger, Richard and Ha, Vincent and Kratz, David and Lin, Michael and Moyer, Jeremy and Tralie, Christopher J.},
  title =	{{Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{62:1--62:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.62},
  URN =		{urn:nbn:de:0030-drops-179129},
  doi =		{10.4230/LIPIcs.SoCG.2023.62},
  annote =	{Keywords: convex hulls, onions, fractional cascading, visualization, d3}
}
Document
DOI: 10.4230/LITES-v004-i001-a004
How Is Your Satellite Doing? Battery Kinetics with Recharging and Uncertainty

Authors: Holger Hermanns, Jan Krčál, and Gilles Nies

Published in: LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1

Abstract
The kinetic battery model is a popular model of the dynamic behaviour of a conventional battery, useful to predict or optimize the time until battery depletion. The model however lacks certain obvious aspects of batteries in-the-wild, especially with respect to the effects of random influences and the behaviour when charging up to capacity limits.This paper considers the kinetic battery model with limited capacity in the context of piecewise constant yet random charging and discharging. We provide exact representations of the battery behaviour wherever possible, and otherwise develop safe approximations that bound the probability distribution of the battery state from above and below. The resulting model enables the time-dependent evaluation of the risk of battery depletion. This is demonstrated in an extensive dependability study of a nano satellite currently orbiting the earth.
Cite as

Holger Hermanns, Jan Krčál, and Gilles Nies. How Is Your Satellite Doing? Battery Kinetics with Recharging and Uncertainty. In LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1, pp. 04:1-04:28, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{hermanns_et_al:LITES-v004-i001-a004,
  author =	{Hermanns, Holger and Kr\v{c}\'{a}l, Jan and Nies, Gilles},
  title =	{{How Is Your Satellite Doing? Battery Kinetics with Recharging and Uncertainty}},
  booktitle =	{LITES, Volume 4, Issue 1 (2017)},
  pages =	{04:1--04:28},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2017},
  volume =	{4},
  number =	{1},
  editor =	{Hermanns, Holger and Kr\v{c}\'{a}l, Jan and Nies, Gilles},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v004-i001-a004},
  doi =		{10.4230/LITES-v004-i001-a004},
  annote =	{Keywords: Battery Power, Depletion Risk, Bounded Charging and Discharging, Stochastic Load, Distribution Bounds}
}
Document
DOI: 10.4230/LITES-v001-i001-a003
Randomized Caches Considered Harmful in Hard Real-Time Systems

Authors: Jan Reineke

Published in: LITES, Volume 1, Issue 1 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 1

Abstract
We investigate the suitability of caches with randomized placement and replacement in the context of hard real-time systems. Such caches have been claimed to drastically reduce the amount of information required by static worst-case execution time (WCET) analysis, and to be an enabler for measurement-based probabilistic timing analysis. We refute these claims and conclude that with prevailing static and measurement-based analysis techniques caches with deterministic placement and least-recently-used replacement are preferable over randomized ones.
Cite as

Jan Reineke. Randomized Caches Considered Harmful in Hard Real-Time Systems. In LITES, Volume 1, Issue 1 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 1, pp. 03:1-03:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{reineke:LITES-v001-i001-a003,
  author =	{Reineke, Jan},
  title =	{{Randomized Caches Considered Harmful in Hard Real-Time Systems}},
  booktitle =	{LITES, Volume 1, Issue 1 (2014)},
  pages =	{03:1--03:13},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2014},
  volume =	{1},
  number =	{1},
  editor =	{Reineke, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v001-i001-a003},
  doi =		{10.4230/LITES-v001-i001-a003},
  annote =	{Keywords: Real-time systems, Caches, Randomization, WCET analysis}
}
  • Refine by Author
  • 1 Berger, Richard
  • 1 Ha, Vincent
  • 1 Hermanns, Holger
  • 1 Kratz, David
  • 1 Krčál, Jan
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Real-time system architecture
  • 1 Computer systems organization → Reliability
  • 1 Hardware → Batteries
  • 1 Hardware → Safety critical systems
  • 1 Human-centered computing → Visualization toolkits
  • Show More...

  • Refine by Keyword
  • 1 Battery Power
  • 1 Bounded Charging and Discharging
  • 1 Caches
  • 1 Depletion Risk
  • 1 Distribution Bounds
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2014
  • 1 2017
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact