@inbook{16406, abstract = {{In order to evaluate the efficiency of algorithms for real-time 3D rendering, different properties like rendering time, occluded triangles, or image quality, need to be investigated. Since these properties depend on the position of the camera, usually some camera path is chosen, along which the measurements are performed. As those measurements cover only a small part of the scene, this approach hardly allows drawing conclusions regarding the algorithm's properties at arbitrary positions in the scene. The presented method allows the systematic and position-independent evaluation of rendering algorithms. It uses an adaptive sampling approach to approximate the distribution of a property (like rendering time) for all positions in the scene. This approximation can be visualized to produce an intuitive impression of the algorithm's behavior or be statistically analyzed for objectively rating and comparing algorithms. We demonstrate our method by evaluating performance aspects of a known occlusion culling algorithm. }}, author = {{Jähn, Claudius and Eikel, Benjamin and Fischer, Matthias and Petring, Ralf and Meyer auf der Heide, Friedhelm}}, booktitle = {{Advances in Visual Computing}}, isbn = {{9783642419133}}, issn = {{0302-9743}}, title = {{{Evaluation of Rendering Algorithms Using Position-Dependent Scene Properties}}}, doi = {{10.1007/978-3-642-41914-0_12}}, year = {{2013}}, } @inbook{16407, abstract = {{Many virtual 3D scenes, especially those that are large, are not structured evenly. For such heterogeneous data, there is no single algorithm that is able to render every scene type at each position fast and with the same high image quality. For a small set of scenes, this situation can be improved if different rendering algorithms are manually assigned to particular parts of the scene by an experienced user. We introduce the Multi-Algorithm-Rendering method. It automatically deploys different rendering algorithms simultaneously for a broad range of scene types. The method divides the scene into subregions and measures the behavior of different algorithms for each region in a preprocessing step. During runtime, this data is utilized to compute an estimate for the quality and running time of the available rendering algorithms from the observer's point of view. By solving an optimizing problem, the image quality can be optimized by an assignment of algorithms to regions while keeping the frame rate almost constant. }}, author = {{Petring, Ralf and Eikel, Benjamin and Jähn, Claudius and Fischer, Matthias and Meyer auf der Heide, Friedhelm}}, booktitle = {{Advances in Visual Computing}}, isbn = {{9783642419133}}, issn = {{0302-9743}}, title = {{{Real-Time 3D Rendering of Heterogeneous Scenes}}}, doi = {{10.1007/978-3-642-41914-0_44}}, year = {{2013}}, } @inproceedings{505, abstract = {{In this paper we introduce “On-The-Fly Computing”, our vision of future IT services that will be provided by assembling modular software components available on world-wide markets. After suitable components have been found, they are automatically integrated, configured and brought to execution in an On-The-Fly Compute Center. We envision that these future compute centers will continue to leverage three current trends in large scale computing which are an increasing amount of parallel processing, a trend to use heterogeneous computing resources, and—in the light of rising energy cost—energy-efficiency as a primary goal in the design and operation of computing systems. In this paper, we point out three research challenges and our current work in these areas.}}, author = {{Happe, Markus and Kling, Peter and Plessl, Christian and Platzner, Marco and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 9th IEEE Workshop on Software Technology for Future embedded and Ubiquitous Systems (SEUS)}}, publisher = {{IEEE}}, title = {{{On-The-Fly Computing: A Novel Paradigm for Individualized IT Services}}}, doi = {{10.1109/ISORC.2013.6913232}}, year = {{2013}}, } @article{579, abstract = {{A left-to-right maximum in a sequence of n numbers s_1, …, s_n is a number that is strictly larger than all preceding numbers. In this article we present a smoothed analysis of the number of left-to-right maxima in the presence of additive random noise. We show that for every sequence of n numbers s_i ∈ [0,1] that are perturbed by uniform noise from the interval [-ε,ε], the expected number of left-to-right maxima is Θ(&sqrt;n/ε + log n) for ε>1/n. For Gaussian noise with standard deviation σ we obtain a bound of O((log3/2 n)/σ + log n).We apply our results to the analysis of the smoothed height of binary search trees and the smoothed number of comparisons in the quicksort algorithm and prove bounds of Θ(&sqrt;n/ε + log n) and Θ(n/ε+1&sqrt;n/ε + n log n), respectively, for uniform random noise from the interval [-ε,ε]. Our results can also be applied to bound the smoothed number of points on a convex hull of points in the two-dimensional plane and to smoothed motion complexity, a concept we describe in this article. We bound how often one needs to update a data structure storing the smallest axis-aligned box enclosing a set of points moving in d-dimensional space.}}, author = {{Damerow, Valentina and Manthey, Bodo and Meyer auf der Heide, Friedhelm and Räcke, Harald and Scheideler, Christian and Sohler, Christian and Tantau, Till}}, journal = {{Transactions on Algorithms}}, number = {{3}}, pages = {{30}}, publisher = {{ACM}}, title = {{{Smoothed analysis of left-to-right maxima with applications}}}, doi = {{10.1145/2229163.2229174}}, year = {{2012}}, } @inproceedings{619, abstract = {{Dynamics in networks is caused by a variety of reasons, like nodes moving in 2D (or 3D) in multihop cellphone networks, joins and leaves in peer-to-peer networks, evolution in social networks, and many others. In order to understand such kinds of dynamics, and to design distributed algorithms that behave well under dynamics, many ways to model dynamics are introduced and analyzed w.r.t. correctness and eciency of distributed algorithms. In [16], Kuhn, Lynch, and Oshman have introduced a very general, worst case type model of dynamics: The edge set of the network may change arbitrarily from step to step, the only restriction is that it is connected at all times and the set of nodes does not change. An extended model demands that a xed connected subnetwork is maintained over each time interval of length T (T-interval dynamics). They have presented, among others, algorithms for counting the number of nodes under such general models of dynamics.In this paper, we generalize their models and algorithms by adding random edge faults, i.e., we consider fault-prone dynamic networks: We assume that an edge currently existing may fail to transmit data with some probability p. We rst observe that strong counting, i.e., each node knows the correct count and stops, is not possible in a model with random edge faults. Our main two positive results are feasibility and runtime bounds for weak counting, i.e., stopping is no longer required (but still a correct count in each node), and for strong counting with an upper bound, i.e., an upper bound N on n is known to all nodes.}}, author = {{Brandes, Philipp and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS)}}, pages = {{9--14}}, title = {{{Distributed Computing in Fault-Prone Dynamic Networks}}}, doi = {{10.1145/2414815.2414818}}, year = {{2012}}, } @inproceedings{636, abstract = {{We consider an online facility location problem where clients arrive over time and their demands have to be served by opening facilities and assigning the clients to opened facilities. When opening a facility we must choose one of K different lease types to use. A lease type k has a certain lease length lk. Opening a facility i using lease type k causes a cost of f k i and ensures that i is open for the next lk time steps. In addition to costs for opening facilities, we have to take connection costs ci j into account when assigning a client j to facility i. We develop and analyze the first online algorithm for this problem that has a time-independent competitive factor.This variant of the online facility location problem was introduced by Nagarajan and Williamson [7] and is strongly related to both the online facility problem by Meyerson [5] and the parking permit problem by Meyerson [6]. Nagarajan and Williamson gave a 3-approximation algorithm for the offline problem and an O(Klogn)-competitive algorithm for the online variant. Here, n denotes the total number of clients arriving over time. We extend their result by removing the dependency on n (and thereby on the time). In general, our algorithm is O(lmax log(lmax))-competitive. Here lmax denotes the maximum lease length. Moreover, we prove that it is O(log2(lmax))-competitive for many “natural” cases. Such cases include, for example, situations where the number of clients arriving in each time step does not vary too much, or is non-increasing, or is polynomially bounded in lmax.}}, author = {{Meyer auf der Heide, Friedhelm and Pietrzyk, Peter and Kling, Peter}}, booktitle = {{Proceedings of the 19th International Colloquium on Structural Information & Communication Complexity (SIROCCO)}}, pages = {{61--72}}, title = {{{An Algorithm for Facility Leasing}}}, doi = {{10.1007/978-3-642-31104-8_6}}, year = {{2012}}, } @inbook{16445, author = {{Kempkes, Barbara and Meyer auf der Heide, Friedhelm}}, booktitle = {{Experimental Algorithms}}, isbn = {{9783642308499}}, issn = {{0302-9743}}, title = {{{Continuous Local Strategies for Robotic Formation Problems}}}, doi = {{10.1007/978-3-642-30850-5_2}}, year = {{2012}}, } @inproceedings{16446, author = {{Kempkes, Barbara and Kling, Peter and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and architectures - SPAA '12}}, isbn = {{9781450312134}}, title = {{{Optimal and competitive runtime bounds for continuous, local gathering of mobile robots}}}, doi = {{10.1145/2312005.2312009}}, year = {{2012}}, } @inbook{16448, author = {{Kempkes, Barbara and Meyer auf der Heide, Friedhelm}}, booktitle = {{Algorithms for Sensor Systems}}, isbn = {{9783642282089}}, issn = {{0302-9743}}, title = {{{Local, Self-organizing Strategies for Robotic Formation Problems}}}, doi = {{10.1007/978-3-642-28209-6_2}}, year = {{2012}}, } @inproceedings{16408, abstract = {{We present a parallel rendering system for heterogeneous PC clusters to visualize massive models. One single, powerful visualization node is supported by a group of backend nodes with weak graphics performance. While the visualization node renders the visible objects, the backend nodes asynchronously perform visibility tests and supply the front end with visible scene objects. The visualization node stores only currently visible objects in its memory, while the scene is distributed among the backend nodes’ memory without redundancy. To efficiently compute the occlusion tests in spite of that each backend node stores only a fraction of the original geometry, we complete the scene by adding highly simplified versions of the objects stored on other nodes. We test our system with 15 backend nodes. It is able to render a ≈ 350,M polygons (≈ 8.5,GiB) large aircraft model with 20, to 30,fps and thus allows a walk-through in real-time. }}, author = {{Suess, Tim and Koch, Clemens and Jähn, Claudius and Fischer, Matthias and Meyer auf der Heide, Friedhelm}}, booktitle = {{Advances in Visual Computing}}, isbn = {{9783642331787}}, issn = {{0302-9743}}, pages = {{502--512}}, title = {{{Asynchronous Occlusion Culling on Heterogeneous PC Clusters for Distributed 3D Scenes}}}, doi = {{10.1007/978-3-642-33179-4_48}}, volume = {{7431}}, year = {{2012}}, } @proceedings{26196, editor = {{Gausemeier, Jürgen and Grafe, Michael and Meyer auf der Heide, Friedhelm}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{10. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung}}}, volume = {{295}}, year = {{2011}}, } @inproceedings{17450, author = {{Suess, Tim and Jähn, Claudius and Fischer, Matthias and Meyer auf der Heide, Friedhelm and Koch, Clemens}}, booktitle = {{Augmented & Virtual Reality in der Produktentstehung}}, pages = {{185----197}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts}}, title = {{{Ein paralleles Out-of-Core Renderingsystem für Standard-Rechnernetze}}}, volume = {{295}}, year = {{2011}}, } @unpublished{18194, abstract = {{We present a parallel rendering system for PC-Clusters to visualize large 3D scenes. One single visualization node, equipped with a high-end graphics adapter, is supported by a group of backend nodes with weak graphics performance. The objects of the scene are distributed among these backend nodes, they serve two purposes: First, they provide an out-of-core memory system for the visualization node. Second, they assist the visualization node's rendering by performing visibility calculations and only sending visible objects to the visualization node. In order to obtain fast rendering with our system, we have to distribute the objects among the backend nodes in a way that does not only guarantee an even distribution of the objects, but also an even distribution of the visibility calculations and the amount of data send to the visualization node. We identify necessary properties of the distribution and argue that a random distribution is a good candidate. Further, in order to reduce the number of objects sent to the visualization node per frame, we employ an approximate hierarchical occlusion culling in each backend node. For this, they are equipped, in addition to the objects assigned to them, with simplified versions of the other objects of the 3D scene. The visualization node is equipped with 512 MiB video memory and supported by 15 backend nodes. This system is able to render a approx. 350 million polygons (approx. 8.5 GiB) large aircraft model between 20 - 30 fps and thus allows a walkthrough in real-time.}}, author = {{Suess, Tim and Koch, Clemens and Jähn, Claudius and Fischer, Matthias and Meyer auf der Heide, Friedhelm}}, title = {{{Parallel Out-of-Core Occlusion Culling}}}, year = {{2011}}, } @inproceedings{664, abstract = {{Web Computing is a variant of parallel computing where the idle times of PCs donated by worldwide distributed users are employed to execute parallel programs. The PUB-Web library developed by us supports this kind of usage of computing resources. A major problem for the efficient execution of such parallel programs is load balancing. In the Web Computing context, this problem becomes more difficult because of the dynamic behavior of the underlying "parallel computer": the set of available processors (donated PCs) as well as their availability (idle times) change over time in an unpredictable fashion.In this paper, we experimentally evaluate and compare load balancing algorithms in this scenario, namely a variant of the well-established Work Stealing algorithm and strategies based on a heterogeneous version of distributed hash-tables (DHHTs) introduced recently. In order to run a meaningful experimental evaluation, we employ, in addition to our Web Computing library PUB-Web, realistic data sets for the job input streams and for the dynamics of the availability of the resources.Our experimental evaluations suggest that Work Stealing is the better strategy if the number of processes ready to run matches the number of available processors. But a suitable variant of DHHTs outperforms Work Stealing if there are significantly more processes ready to run than available processors.}}, author = {{Gehweiler, Joachim and Kling, Peter and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM)}}, pages = {{31----40}}, title = {{{An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment}}}, doi = {{10.1007/978-3-642-31500-8_4}}, year = {{2011}}, } @proceedings{667, editor = {{Meyer auf der Heide, Friedhelm and Rajaraman, Rajmohan }}, title = {{{23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures}}}, doi = {{10.1145/1989493}}, year = {{2011}}, } @inproceedings{16410, abstract = {{Gathering n mobile robots in one single point in the Euclidean plane is a widely studied problem from the area of robot formation problems. Classically, the robots are assumed to have no physical extent, and they are able to share a position with other robots. We drop these assumptions and investigate a similar problem for robots with (a spherical) extent: the goal is to gather the robots as close together as possible. More exactly, we want the robots to form a sphere with minimum radius around a predefined point. We propose an algorithm for this problem which synchronously moves the robots towards the center of the sphere unless they block each other. In this case, if possible, the robots spin around the center of the sphere. We analyze this algorithm experimentally in the plane. If R is the distance of the farthest robot to the center of the sphere, the simulations indicate a runtime which is linear in n and R. Additionally, we prove a theoretic upper bound for the runtime of O(nR) for a discrete version of the problem. Simulations also suggest a runtime of O(n + R) for the discrete version.}}, 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 = {{37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011)}}, isbn = {{9783642183805}}, issn = {{0302-9743}}, number = {{6543}}, pages = {{178--189}}, publisher = {{Springer}}, title = {{{Collisionless Gathering of Robots with an Extent}}}, doi = {{10.1007/978-3-642-18381-2_15}}, year = {{2011}}, } @inbook{16412, author = {{Gehweiler, Joachim and Meyer auf der Heide, Friedhelm}}, booktitle = {{Algorithms Unplugged}}, isbn = {{9783642153273}}, pages = {{367--374}}, title = {{{Bin Packing - How Do I Get My Stuff into the Boxes}}}, doi = {{10.1007/978-3-642-15328-0_38}}, year = {{2011}}, } @inproceedings{16428, author = {{Rajaraman, Rajmohan and Meyer auf der Heide, Friedhelm}}, isbn = {{9781450307437}}, title = {{{Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11}}}, doi = {{10.1145/1989493}}, year = {{2011}}, } @article{16447, author = {{Degener, Bastian and Fekete, Sándor P. and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}}, issn = {{1574-0137}}, journal = {{Computer Science Review}}, pages = {{57--68}}, title = {{{A survey on relay placement with runtime and approximation guarantees}}}, doi = {{10.1016/j.cosrev.2010.09.005}}, year = {{2011}}, } @inproceedings{16451, author = {{Brandes, Philipp and Degener, Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}}, booktitle = {{SIROCCO '11: Proc. of the 18th International Colloquium on Structural Information and Communication Complexity}}, pages = {{138--149}}, title = {{{Energy-efficient strategies for building short chains of mobile robots locally}}}, doi = {{10.1016/j.tcs.2012.10.056}}, year = {{2011}}, }