@inproceedings{16453, author = {{Degener, Bastian and Kempkes, Barbara and Langner, Tobias and Meyer auf der Heide, Friedhelm and Pietrzyk, Peter and Wattenhofer, Roger}}, booktitle = {{Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11}}, isbn = {{9781450307437}}, title = {{{A tight runtime bound for synchronous gathering of autonomous robots with limited visibility}}}, doi = {{10.1145/1989493.1989515}}, year = {{2011}}, } @inproceedings{16454, author = {{Kling, Peter and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11}}, isbn = {{9781450307437}}, title = {{{Convergence of local communication chain strategies via linear transformations}}}, doi = {{10.1145/1989493.1989517}}, year = {{2011}}, } @article{16455, author = {{Degener, Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}}, issn = {{1877-0509}}, journal = {{Procedia Computer Science}}, pages = {{153--155}}, title = {{{Building Simple Formations in Large Societies of Tiny Mobile Robots}}}, doi = {{10.1016/j.procs.2011.09.049}}, year = {{2011}}, } @inbook{16456, author = {{Degener, Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}}, booktitle = {{Organic Computing — A Paradigm Shift for Complex Systems}}, isbn = {{9783034801294}}, title = {{{Energy-Awareness in Self-organising Robotic Exploration Teams}}}, doi = {{10.1007/978-3-0348-0130-0_35}}, year = {{2011}}, } @inbook{16459, author = {{Brandes, Philipp and Degener, Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}}, booktitle = {{Structural Information and Communication Complexity}}, isbn = {{9783642222115}}, issn = {{0302-9743}}, title = {{{Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally}}}, doi = {{10.1007/978-3-642-22212-2_13}}, year = {{2011}}, } @article{17009, author = {{Hsu, D. Frank and Magga, Bruce M. and Ho, Howard C. T. and Hromkovic, Juraj and Lau, Francis C. M. and Meyer auf der Heide, Friedhelm}}, issn = {{0219-2659}}, journal = {{Journal of Interconnection Networks}}, pages = {{vii--viii}}, title = {{{EDITORIAL}}}, doi = {{10.1142/s0219265911002885}}, year = {{2011}}, } @inbook{16409, abstract = {{Given a set of n mobile robots in the d-dimensional Euclidean space, the goal is to let them converge to a single not predefined point. The challenge is that the robots are limited in their capabilities. Robots can, upon activation, compute the positions of all other robots using an individual affine coordinate system. The robots are indistinguishable, oblivious and may have different affine coordinate systems. A very general discrete time model assumes that robots are activated in arbitrary order. Further, the computation of a new target point may happen much earlier than the movement, so that the movement is based on outdated information about other robot's positions. Time is measured as the number of rounds, where a round ends as soon as each robot has moved at least once. In [Cohen, Peleg: Convergence properties of gravitational algorithms in asynchronous robot systems], the Center of Gravity is considered as target function, convergence was proven, and the number of rounds needed for halving the diameter of the convex hull of the robot's positions was shown to be O(n^2) and Omega(n). We present an easy-to-check property of target functions that guarantee convergence and yields upper time bounds. This property intuitively says that when a robot computes a new target point, this point is significantly within the current axes aligned minimal box containing all robots. This property holds, e.g., for the above-mentioned target function, and improves the above O(n^2) to an asymptotically optimal O(n) upper bound. Our technique also yields a constant time bound for a target function that requires all robots having identical coordinate axes. }}, author = {{Cord-Landwehr, Andreas and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes, Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus and Meyer auf der Heide, Friedhelm and Raupach, Christoph and Swierkot, Kamil and Warner, Daniel and Weddemann, Christoph and Wonisch, Daniel}}, booktitle = {{Automata, Languages and Programming}}, isbn = {{9783642220111}}, issn = {{0302-9743}}, title = {{{A New Approach for Analyzing Convergence Algorithms for Mobile Robots}}}, doi = {{10.1007/978-3-642-22012-8_52}}, year = {{2011}}, } @techreport{17462, author = {{Gehweiler, Joachim and Meyer auf der Heide, Friedhelm and Schroeder, Ulf-Peter}}, publisher = {{Heinz Nixdorf Institut}}, title = {{{A Large-Scale Distributed Environment for Peer-to-Peer Services}}}, year = {{2010}}, } @techreport{17464, author = {{Blesa, Maria J. and Blum, Christian and de Caro, Angelo and Degener, Bastian and Kempkes, Barbara and Leone, Piere and Persiano, Giuseppe and Meyer auf der Heide, Friedhelm and Mylonas, Georgios}}, title = {{{Adapting a sensor net to the dynamic environment in a wildlife scenario - a case study}}}, year = {{2010}}, } @unpublished{17586, abstract = {{We are given a winding chain of $n$ mobile robots between two stations in the plane, each of them having a limited viewing range. It is only guaranteed that each robot can see its two neighbors in the chain. We analyze a simple and natural parallel strategy to shorten the chain in a time model where each relay is allowed to move up to a distance of $\delta$ in each time step. This model fills the gap between the previously used discrete time model and the continuous time model which was introduced recently in \cite{sirocco}. We analyze the strategy with respect to two quality measures: the number of time steps and the maximum distance to be traveled by the robots, which are the major energy consumers in this scenario. We provide asymptotically tight or almost tight bounds in this time model for both quality measures and it turns out that the best choice for $\delta$ is $\delta \in \Theta(\frac{1}{n})$, since this minimizes the number of time steps as well as the maximum traveled distance.}}, author = {{Brandes, Philipp and Degener, Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}}, title = {{{Building short chains of mobile robots locally with a bounded stepwidth}}}, year = {{2010}}, } @article{1903, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, journal = {{Informatik Spektrum}}, number = {{5}}, pages = {{468----474}}, title = {{{Algorithmische Grundlagen verteilter Speichersysteme}}}, doi = {{10.1007/s00287-010-0470-2}}, year = {{2010}}, } @inproceedings{16414, author = {{Meyer auf der Heide, Friedhelm and Phillips, Cynthia A.}}, isbn = {{9781450300797}}, title = {{{Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures - SPAA '10}}}, doi = {{10.1145/1810479}}, year = {{2010}}, } @inbook{16365, author = {{Degener, Bastian and Kempkes, Barbara and Kling, Peter and Meyer auf der Heide, Friedhelm}}, booktitle = {{Structural Information and Communication Complexity}}, isbn = {{9783642132834}}, issn = {{0302-9743}}, pages = {{168--182}}, title = {{{A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots}}}, doi = {{10.1007/978-3-642-13284-1_14}}, year = {{2010}}, } @inproceedings{16401, author = {{Degener, Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures - SPAA '10}}, isbn = {{9781450300797}}, title = {{{A local O(n2) gathering algorithm}}}, doi = {{10.1145/1810479.1810523}}, year = {{2010}}, } @book{16403, editor = {{Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.}}, isbn = {{9783642141614}}, issn = {{0302-9743}}, title = {{{Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II.}}}, doi = {{10.1007/978-3-642-14162-1}}, year = {{2010}}, } @book{16404, editor = {{Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.}}, isbn = {{9783642141614}}, issn = {{0302-9743}}, title = {{{Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I.}}}, doi = {{10.1007/978-3-642-14165-2}}, year = {{2010}}, } @article{17453, author = {{Meyer auf der Heide, Friedhelm and Rammig, Franz-Josef}}, journal = {{Public Service Review: Science and Technology}}, title = {{{Self-Organisation and Self-Optimization}}}, volume = {{04}}, year = {{2009}}, } @inproceedings{18346, abstract = {{For a fixed virtual scene (=collection of simplices) S and given observer position p, how many elements of S are weakly visible (i.e. not fully occluded by others) from p? The present work explores the trade-off between query time and preprocessing space for these quantities in 2D: exactly, in the approximate deterministic, and in the probabilistic sense. We deduce the EXISTENCE of an O(m^2/n^2) space data structure for S that, given p and time O(log n), allows to approximate the ratio of occluded segments up to arbitrary constant absolute error; here m denotes the size of the Visibility Graph--which may be quadratic, but typically is just linear in the size n of the scene S. On the other hand, we present a data structure CONSTRUCTIBLE in O(n*log(n)+m^2*polylog(n)/k) preprocessing time and space with similar approximation properties and query time O(k*polylog n), where k