Experimental analysis of adjustable sectorized topologies for static ad hoc networks - Volbert, Klaus (Proceedings of the 2004 joint workshop on Foundations of mobile computing - DIALM-POMC '04)

Traffic and Hop Efficient Position-based Routing using a Cell Structure - Rührup, Stefan; Schindelhauer, Christian

V:Drive - Costs and Benefits of an Out-of-Band Storage Virtualization System - Brinkmann, André; Heidebuer, Michael; Meyer auf der Heide, Friedhelm; Rückert, Ulrich; Salzwedel, Kay; Vodisek, Mario (21st IEEE Conference on Mass Storage Systems and Technologies / 12th NASA Goddard Conference on Mass Storage Systems and Technologies, Greenbelt, Maryland, USA)

Smoothed Number of Extreme Points under Uniform Noise - Sohler, Christian; Damerow, Valentina (Proceedings of the 20th European Workshop on Computational Geometry (EWCG'04))

Extreme Points Under Random Noise - Damerow, Valentina; Sohler, Christian (Proceedings of the 12th European Symposium on Algorithms (ESA'04))
Given a point set P in the d-dimensional unit hypercube, we give upper bounds on the maximal expected number of extreme points when each point is perturbed by small random noise chosen independently for each point from the same noise distribution Δ. Our results are parametrized by the variance of the noise distribution. For large variance we essentially consider the average case for distribution Δ while for variance 0 we consider the worst case. Hence our results give upper bounds on the number of extreme points where our input distributions range from average case to worst case. Our main contribution is a rather general lemma that can be used to obtain upper bounds on the expected number of extreme points for a large class of noise distributions. We then apply this lemma to obtain explicit bounds for random noise coming from the Gaussian normal distribution of variance σ² and the uniform distribution in a hypercube of side length &epsilon. For these noise distributions we show upper bounds of O( (1/ σ )^d * log^3/2 * d - 1 n ) and O( ( (n log n) / ε )^d/(d+1) ), respectively. Besides its theoretical motivation our model is also motivated by the observation that in many applications of convex hull algorithms the input data is inherently noisy, e.g. when the data comes from physical measurement or imprecise arithmetic is used.

Reducing State Changes with a Pipeline Buffer - Sohler, Christian; Krokowski, Jens; Räcke, Harald; Westermann, Matthias (Proceedings of the Vision, Modeling, and Visualization Conference (VMV 2004))
A limiting factor in the performance of a render- ing system is the number of state changes, i.e., changes of the attributes material, texture, shader program, etc., in the stream of rendered primitives. We propose to include a small buffer between appli- cation and graphics hardware in the rendering sys- tem. This pipeline buffer is used to rearrange the incoming sequence of primitives on-line and locally in such a way that the number of state changes is minimized. This method is generic; it can be easily integrated into existing rendering systems. In our experiments a pipeline buffer reduces the number of state changes by an order of magnitude and achieves almost the same rendering time as an optimal, i.e., presorted, sequence without pipeline buffer. Due to its simple structure and its low mem- ory requirements this method can easily be imple- mented in software or even hardware.

Sublinear-Time Approximation for Clustering via Random Sampling - Sohler, Christian; Czumaj, Artur (Automata, Languages and Programming (ICALP))

Computability in linear algebra - Ziegler, Martin; Brattka, Vasco (Theoretical Computer Science)

Computable operators on regular sets - Ziegler, Martin (Computability and Complexity in Analysis)
For uniform computability of regular sets in Euclidean space, previous work has identified twelve 'basic' notions, to (pairs of) which many previous notions considered in literature were shown to be equivalent. With respect to those basic notions, we now investigate on the computability of natural OPERATIONS on regular sets: union, intersection, complement, convex hull, image, and pre-image under suitable classes of functions.

Fast Multipoint Evaluation of Bivariate Polynomials - Nüsken, Michael; Ziegler, Martin (Proc. 12th Annual Symposium on Algorithms (ESA'04))
We generalize univariate multipoint evaluation of polynomials of degree n at sublinear amortized cost per point. More precisely, it is shown how to evaluate a bivariate polynomial p of maximum degree less than n, specified by its n^2 coefficients, simultaneously at n^2 given points using a total of O(n^2.667) arithmetic operations. In terms of the input size N being quadratic in n, this amounts to an amortized cost of O(N^0.334) per point.

Spanners, Weak Spanners, and Power Spanners for Wireless Networks - Schindelhauer, Christian; Volbert, Klaus; Ziegler, Martin (Proc. of 15th Annual International Symposium on Algorithms and Computation (ISAAC'04))
For $c in REAL$, a $c$-spanner is a subgraph of a complete Euclidean graph satisfying that between any two vertices there exists a path of weighted length at most $c$ times their geometric distance. Based on this property to approximate a complete weighted graph, sparse spanners have found many applications, e.g., in FPTAS, geometric searching, and radio networks. For geometric searching, it turned out to suffice whether the radius rather than the length of some path between any two vertices is bounded relatively to their geometric distance; this is the defining property of weak spanners. Finally regarding radio network applications, a power spanner accounts for the total energy afforded for a wireless transmission with the requirement that the sum of the squares of the lengths of some path between any two planar vertices must be bounded relatively to the square of their geometric distance (or higher powers up to 6 or even 8). While it is known that any $c$-spanner is also both a weak $C_1$-spanner and a $C_2$-power spanner (for appropriate $C_1,C_2$ depending only on $c$ but not on the graph under consideration), we show that the converse fails: There exists a family of $c_1$-power spanners that are no weak $C$-spanners and also a family of weak $c_2$-spanners that are no $C$-spanners for any fixed $C$ (and thus no uniform spanners, either). However the deepest result of the present work reveals that, surprisingly, any weak spanner is also a uniform power spanner. We further generalize the latter notion by considering $(c,delta)$-power spanners where the sum of the $delta$-th powers of the lengths has to be bounded; so $(cdot,2)$-power spanners coincide with the usual power spanners and $(cdot,1)$-power spanners are classical spanners. Interestingly, these $(cdot,delta)$-power spanners form a strict hierarchy where the above results still hold for any $deltageq2$; some even hold for $delta>1$ while counterexamples reveal others to fail for $delta<2$. In fact we show that in general every self-similar curve of fractal dimension $d>delta$ is no $(C,delta)$-power spanner for any fixed $C$.

Guidance of Users in Interactive 3D-Visualisations of Material Flow Simulations - Mueck, Bengt; Dangelmaier, Wilhelm; Laroque, Christoph; Fischer, Matthias; Kortenjan, Michael (Simulation and Visualisation 2004)
The visualisation of manufacturing-processes assists the user in understanding and analysis. Typically he can move free and unguided in a virtual environment which visualizes the entire process. Thus knowledge and conclusions are to some extend acquired on a random base. This article describes the development of a tool, which enables the user to interactively improve significant production processes in the simulation. He moves in a virtual 3D-environment (walkthrough system) and is able to acquire automatically calculated indications for significant processes. At the same time the simulation considers significant objects in a more detailed way. If the viewer is interested in a significant process, he is automatically guided to the relevant location where he can examine the critical situation by modification of the simulation model.

Transcoding von Webinhalten - Oesterdiekhoff, Brigitte (Informatik Spektrum)

Internet Premium Services for Flexible Format Distributed Devices - Oesterdiekhoff, Brigitte (Proceedings of IFIP Working Conference on Distributed and Parallel Embedded Systems (DIPES'04))

Labeling Smart Dust - Bansal, Vikas; Meyer auf der Heide, Friedhelm; Sohler, Christian (12th Annual European Symposium on Algorithms (ESA 2004))
Given n distinct points p1, p2, ... , pn in the plane, the map labeling problem with four squares is to place n axis-parallel equi-sized squares Q1, ... ,Qn of maximum possible size such that pi is a corner of Qi and no two squares overlap. This problem is NP-hard and no algorithm with approximation ratio better than 1/2 exists unless P = NP [10]. In this paper, we consider a scenario where we want to visualize the information gathered by smart dust, i.e. by a large set of simple devices, each consisting of a sensor and a sender that can gather sensor data and send it to a central station. Our task is to label (the positions of) these sensors in a way described by the labeling problem above. Since these devices are not positioned accurately (for example, they might be dropped from an airplane), this gives rise to consider the map labeling problem under the assumption, that the positions of the points are not fixed precisely, but perturbed by random noise. In other words, we consider the smoothed complexity of the map labeling problem. We present an algorithm that, under such an assumption and Gaussian random noise with sufficiently large variance, has linear smoothed complexity.

Fighting against two adversaries - Bienkowski, Marcin; Korzeniowski, Miroslaw; Meyer auf der Heide, Friedhelm (Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures - SPAA '04)

Congestion, Dilation, and Energy in Radio Networks - Meyer auf der Heide, Friedhelm; Schindelhauer, Christian; Volbert, Klaus; Grünewald, Matthias (Theory of Computing Systems)

Scheduling against an adversarial network - Leonardi, S.; Marchetti-Spaccamela, A.; Meyer auf der Heide, Friedhelm (SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures)

The Randomized Sample Tree: A Data Structure for Interactive Walk-Throughs in Externally Stored Virtual Environments - Klein, Jan; Krokowski, Jens; Fischer, Matthias; Wand, Michael; Wanka, Rolf; Meyer auf der Heide, Friedhelm (Presence: Teleoperators and Virtual Environments)
We present a new data structure for rendering highly complex virtual environments of arbitrary topology. The special feature of our approach is that it allows an interactive navigation in very large scenes (30 GB/400 million polygons in our benchmark scenes) that cannot be stored in main memory, but only on a local or remote hard disk. Furthermore, it allows interactive rendering of substantially more complex scenes by instantiating objects. The sampling process is done in the preprocessing. There, the polygons are randomly distributed in our hierarchical data structure, the randomized sample tree. This tree only uses space that is linear in the number of polygons. In order to produce an approximate image of the scene, the tree is traversed and polygons stored in the visited nodes are rendered. During the interactive walkthrough, parts of the sample tree are loaded from local or remote hard disk. We implemented our algorithm in a prototypical walkthrough system. Analysis and experiments show that the quality of our images is comparable to images computed by the conventional z-buffer algorithm regardless of the scene topology.

Sensor Networks with More Features Using Less Hardware - Liu Jing, Michelle; Ruehrup, Stefan; Schindelhauer, Christian; Volbert, Klaus; Dierkes, Martin; Bellgardt, Andreas; Ibers, Rüdiger; Hilleringmann, Ulrich ({GOR/NGB Conference Tilburg 2004})

The Paderborn University BSP (PUB) library - Bonorden, Olaf; Juurlink, Bernhardus; von Otte, Ingo; Rieping, Ingo (Parallel Computing)
The Paderborn University BSP (PUB) library is a C communication library based on the BSP model. The basic library supports buffered as well as unbuffered non-blocking communication between any pair of processors and a mechanism for synchronizing the processors in a barrier style. In addition, PUB provides non-blocking collective communication operations on arbitrary subsets of processors, the ability to partition the processors into independent groups that execute asynchronously from each other, and a zero-cost synchronization mechanism. Furthermore, some techniques used in the implementation of the PUB library deviate significantly from the techniques used in other BSP libraries.

Algorithmic Approaches for Storage Networks - Salzwedel, Kay A. (Algorithms for Memory Hierarchies)

Storage Management as Means to cope with Exponential Information Growth - Scheideler, Christian; Salzwedel, Kay; Meyer auf der Heide, Friedhelm; Brinkmann, André; Vodisek, Mario; Rückert, Ulrich (Proceedings of SSGRR 2003)
The advances in Internet technology have led to tremendous improvements in business, education, and science and have changed the way we think, live, and communicate. Information exchange has become ubiquitous by the possibilities offered through modern technologies. We are able to offer information 24 hours a day through our web sites and can leave messages every time and from anywhere in the world. This change in communication has led to new challenges. Enterprises have to deal with an information amount that doubles every year. The technological foundation to cope with this information explosion is given by Storage Area Networks (SANs), which are able to connect a great number of storage systems over a fast interconnection network. However, to be able to use the benefits of a SAN, an easy-to-use and efficient management support has to be given to the storage administrator. In this paper, we will suggest new storage management concepts and we will introduce a new management environment that is able to significantly reduce management costs and increases the performance and resource utilization of the given SAN infrastructure.

Performance of distributed algorithms for topology control in wireless networks - Rührup, Stefan; Schindelhauer, Christian; Volbert, Klaus; Grünewald, M. (Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS))
We try to close the gap between theoretical investigations of wireless network topologies and realistic wireless environments. For point-to-point communication, we examine theoretically well-analyzed sparse graphs, i.e. the Yao-graph, the SparsY-graph, and the SymmY-graph. We present distributed algorithms that can be used to build up these graphs in time $O(log n)$ per node without the use of any geo-graphical positioning system. Our algorithms are based only on local knowledge and local decisions and make use of power control to establish communication links with low energy-cost. We compare these algorithms with respect to congestion, dilation, and energy. For congestion we introduce different measures that allow us to investigate the difference between real-world wireless networks and models for wireless communication at a high level of abstraction. For more realistic simulations we extend our simulation environment SAHNE. We use a realistic transmission model for directed communication that uses sector subdivision. Finally, our experimental results show that our topologies and algorithms work well in a distributed environment and we give some recommendations for the topology control based on our simulations.

Implementierung und Vergleich von Verfahren zum Information Retrieval im World Wide Web - Mahlmann, Peter

Directed power-variable infrared communication for the mini robot Khepera - Volbert, Klaus; Grünewald, Matthias; Schindelhauer, Christian; Rückert, Ulrich (Proceedings of the 2nd International Conference on Autonomous Minirobots for Research and Edutainment)
Communication facilities are important in Robotics if several robots have to work together. In this paper, we describe problems and solutions encountered while designing an infrared-based communication device for the mini robot Khepera. In contrast to traditional omnidirectional systems, it features directed, power-variable transmission in eight directions at unit[23.4]kbps up to a range of unit[1m]. It can differentiate incoming data signals from interference from adjacent sectors and can estimate their direction-of-arrival. We model the transmission over the infrared channel and show how interference influences the reception of the data signals. We also describe methods how to reduce these effects. We have tested the performance of the resulted signal processing in a worst case scenario by simulations and in experiments with a prototype implementation. The resulted module is especially suited for experimental evaluation of ad hoc network protocols and for position estimation.

ADB-Trees: Controlling the Error of Time-Critical Collision Detection - Klein, Jan; Zachmann, Gabriel (Proc. 8th International Fall Workshop Vision, Modeling, and Visualization (VMV 2003))
We present a novel framework for hierarchical collision detection that can be applied to virtually all bounding volume (BV) hierarchies. It allows an application to trade quality for speed. Our algorithm yields an estimation of the quality, so that applications can specify the desired quality. In a timecritical system, applications can specify the maximum time budget instead, and quantitatively assess the quality of the results returned by the collision detection afterwards.

Time-Critical Collision Detection Using an Average-Case Approach - Klein, Jan; Zachmann, Gabriel (Proc. ACM Symposium on Virtual Reality Software and Technology (VRST 2003))

Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up - Fomin, Fedor V.; Thilikos, Dimitrios M. (Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003))
Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph Algorithms community about this theory is that it is mainly of theoretical importance. The main purpose of this paper is to show how very deep min-max and duality theorems from Graph Minors can be used to obtain essential speed-up to many known algorithms on different domination problems.

Verteiltes Rendern durch dynamische Bildaufteilung - Terbahl, Martina; Krokowski, Jens (Proceedings of 5. GI-Informatiktage 2003)

Stability versus Speed in a Computable Algebraic Model - Ziegler, Martin (Proc. 5th Conference on Real Numbers and Computers (RNC5), INRIA)

Computable Operators on Regular Sets - Ziegler, Martin (Computability and Complexity in Analysis)

Smoothed Motion Complexity - Damerow, Valentina; Meyer auf der Heide, Friedhelm; Räcke, Harald; Scheideler, Christian; Sohler, Christian (ESA)

Anycasting in Adversarial Systems: Routing and Admission Control - Awerbuch, Baruch; Brinkmann, André; Scheideler, Christian (ICALP)

Components for the Active Support of the Analysis of Material Flow Simulations in a Virtual Environment - Mueck, Bengt; Dangelmaier, Wilhelm; Fischer, Matthias (15th European Simulation Symposium (ESS 2003))

Sublinear Approximation of Euclidean Minimum Spanning Tree - Magen, Avner; Ergun, Funda; Sohler, Christian; Rubinfeld, Ronitt; Czumaj, Artur; Newman, Ilan; Fortnow, Lance (Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003))
We consider the problem of finding the weight of a Euclidean minimum spanning tree for a set of n points in ℝd. We focus on the situation when the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within 1 + ε using only Õ(√ poly(1/ε)) queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbors queries.

A practical algorithm for constructing oblivious routing schemes - Bienkowski, Marcin; Korzeniowski, Miroslaw; Räcke, Harald (Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '03)
In a (randomized) oblivious routing scheme the path chosen for a request between a source $s$ and a target $t$ is independent from the current traffic in the network. Hence, such a scheme consists of probability distributions over $s-t$ paths for every source-target pair $s,t$ in the network. In a recent result citeR02 it was shown that for any undirected network there is an oblivious routing scheme that achieves a polylogarithmic competitive ratio with respect to congestion. Subsequently, Azar et al. citeACF+03 gave a polynomial time algorithm that for a given network constructs the best oblivious routing scheme, i.e. the scheme that guarantees the best possible competitive ratio. Unfortunately, the latter result is based on the Ellipsoid algorithm; hence it is unpractical for large networks. In this paper we present a combinatorial algorithm for constructing an oblivious routing scheme that guarantees a competitive ratio of $O(log^4n)$ for undirected networks. Furthermore, our approach yields a proof for the existence of an oblivious routing scheme with competitive ratio $O(log^3n)$, which is much simpler than the original proof from citeR02.

A Petri Net Model for the Network Layer of a Mobile Ad Hoc Network Architecture - Rust, Carsten; Stappert, Friedhelm; Lukovszki, Tamás (7th World Multiconference on Systemics, Cybernetics and Informatics)
In this paper, we define a Petri net model for the network or routing layer of a mobile ad hoc network. Such networks require routing strategies substantially different from those used in static communication networks. The model pre- sented consists of two layers, a location service and a po- sition based routing. Both are described in detail. Our ap- proach considers a very strong definition of fault tolerance thereby improving state-of-the-art ad hoc routing protocols in several respects. Modeling of the communication archi- tecture for mobile ad hoc networks is part of our overall effort towards a design methodology for distributed embed- ded real-time systems including dynamically evolving com- ponents.

Worst case mobility in ad hoc networks - Schindelhauer, Christian; Lukovszki, Tamás; Rührup, Stefan; Volbert, Klaus (Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03))
We investigate distributed algorithms for mobile ad hoc networks for moving radio stations with adjustable transmission power in a worst case scenario. We consider two models to find a reasonable restriction on the worst-case mobility. In the pedestrian model we assume a maximum speed $v_max$ of the radio stations, while in the vehicular model we assume a maximum acceleration $a_max$ of the points. Our goal is to maintain persistent routes with nice communication network properties like hop-distance, energy-consumption, congestion and number of interferences. A route is persistent, if we can guarantee that all edges of this route can be uphold for a given time span $Delta$, which is a parameter denoting the minimum time the mobile network needs to adopt changes, i.e. update routing tables, change directory entries, etc. This $Delta$ can be used as the length of an update interval for a proactive routing scheme. We extend some known notions such as transmission range, interferences, spanner, power spanner and congestion to both mobility models and introduce a new parameter called crowdedness that states a lower bound on the number of radio interferences. Then we prove that a mobile spanner hosts a path system that polylogarithmically approximates the optimal congestion. We present distributed algorithms based on a grid clustering technique and a high-dimensional representation of the dynamical start situation which construct mobile spanners with low congestion, low interference number, low energy-consumption, and low degree. We measure the optimality of the output of our algorithm by comparing it with the optimal choice of persistent routes under the same circumstances with respect to pedestrian or vehicular worst-case movements. Finally, we present solutions for dynamic position information management under our mobility models.

Optimal oblivious routing in polynomial time - Azar, Yossi; Cohen, Edith; Fiat, Amos; Kaplan, Haim; Racke, Harald (Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC '03)
A recent seminal result of Räcke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. Unfortunately, Räcke's construction is not polynomial time. We give a polynomial time construction that guarantees Räcke's bounds, and more generally gives the true optimal ratio for any (undirected or directed) network.

Entwurf und Implementierung einer Laufzeitumgebung für parallele Algorithmen in Java - Gehweiler, Joachim
In dieser Studienarbeit wurde ein System entworfen und implementiert, das der Ausführung paralleler Algorithmen nach dem Bulk-Synchronous Parallel (BSP)-Modell dient. Von der Paderborn University BSP Library (PUB) unterscheidet es sich dadurch, dass es vom Einsatzgebiet her nicht für Parallelrechner konzipiert ist, sondern vielmehr für eine Ansammlung von PCs und Workstations, die über das gesamte Internet verteilt sind. Gegenüber anderen bekannten Web-Computing Projekten wie z.B. SETI@home oder distributed.net zeichnet sich dieses System dadurch aus, dass nicht Clients von einem zentralen Server "häppchenweise" unabhängige Teilprobleme anfordern und lösen, sondern dass die Clients gemeinsam an einem Problem arbeiten, indem sie nach dem BSP-Modell miteinander kommunizieren und sich synchronisieren.

Definition and Behavior of Langton's Ant in Three Dimensions - Hamann, Heiko (Complex Systems)

Quasi-optimal Arithmetic for Quaternion Polynomials - Ziegler, Martin (Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC'03))
Fast algorithms for arithmetic on real or complex polynomials are well-known and have proven to be not only asymptotically efficient but also very practical. Based on FAST FOURIER TRANSFORM, they for instance multiply two polynomials of degree up to N or multi-evaluate one at N points simultaneously within quasi-linear time O(N polylog N). An extension to (and in fact the mere definition of) polynomials over fields R and C to the SKEW-field H of quaternions is promising but still missing. The present work proposes three approaches which in the commutative case coincide but for H turn out to differ, each one satisfying some desirable properties while lacking others. For each notion, we devise algorithms for according arithmetic; these are quasi-optimal in that their running times match lower complexity bounds up to polylogarithmic factors.

Fast Relative Approximation of Potential Fields - Ziegler, Martin (Lecture Notes in Computer Science)
Multi-evaluation of the Coulomb potential induced by N particles is a central part of N-body simulations. In 3D, known subquadratic time algorithms return approximations up to given ABSOLUTE precision. By combining data structures from Computational Geometry with fast polynomial arithmetic, the present work obtains approximations of prescribable RELATIVE error e>0 in time O(1/e*N*polylog N).

Virtual and Augmented Reality Support for Discrete Manufacturing System Simulation - Fischer, Matthias; Grafe, Michael; Matysczok, Carsten; Mueck, Bengt; Schoo, Michael (Human Aspects in Production Management - Proceedings of the IFIP WG 5.7 Working Conference on Human Aspects in Production Management)
Unternehmen operieren zunehmend in einem schwierigen Umfeld: Die Innovationsdynamik nimmt zu; die Produktlebenszyklen werden kürzer; gleichzeitig werden die Produkte komplexer; der harte Wettbewerb zwingt die Unternehmen, auf Marktveränderungen zu reagieren. Aus dieser Entwicklung resultieren hohe Anforderungen an die Gestaltung der Fertigungsprozesse. Im Wesentlichen kommt es darauf an, die Fertigungsprozesse möglichst rasch an die neuen Gegebenheiten anzupassen, bzw. neue Fertigungsprozesse so zu planen, dass sie auf Anhieb die erforderlichen Resultate bringen. Ein wichtiges Mittel hierfür der Einsatz von Materialflusssimulationen. Hierzu ist zunächst die Erstellung eines Simulationsmodells notwendig. Dafür wird in einem ersten Schritt das zu betrachtende System analysiert und ein rechnerinternes Modell erzeugt. Dieses beinhaltet die Modellierung von Funktionen, Prozessen, Verhaltensweisen oder Regeln, die im Modell die tatsächlichen Wirkzusammenhänge im Unternehmen widerspiegeln sollen. Die so modellierten Aspekte sind untereinander so vernetzt, dass alle Funktionen des Modells ein Ganzes ergeben. Für viele Fragenstellungen werden umfangreiche Modelle mit einem komplexen Verhalten benötigt. Andererseits steigt mit zunehmender Größe und Komplexität des Simulationsmodells auch der Modellierungsaufwand, die Fehleranfälligkeit, die Laufzeit und der Interpretationsaufwand bei der Ergebnisauswertung. Fehler bei der Modellbildung führen bei der Simulation zu Fehlinterpretationen und falschen Ergebnissen. Einen wesentlichen Anteil daran hat die Gestaltung der Benutzungsschnittstelle: Das übliche, wenig intuitive WIMP-Interface (Windows, Icons, Mouse, Pointer) erfordert sehr gut geschulte Benutzer, sodass die Erzeugung der meist komplexen Simulationsmodelle mit großen Zeitaufwand verbunden ist. Die Präsentation der Simulationsergebnisse erfolgt in Form von Wertetabellen und zweidimensionalen, abstrakten Darstellungen des Fertigungssystems. Für die Simulationsexperten erscheint dies ausreichend, für ein aus verschiedenen Bereichen und Disziplinen zusammengesetztes Planungsteam ist das aber nicht akzeptabel. So können Fehlinterpretationen aufgrund der unklaren Darstellungen auftreten. Durch eine durchgängige Unterstützung von der Modellierung über die Ausführung bis zur Analyse von Simulationen durch Augmented-Reality und Virtual-Reality werden viele dieser Probleme überwunden aber viele neue Probleme entstehen. Marktgängige Simulatoren unterstützen zwar z.T. schon Virtual Reality; eine durchgängige Simulationsunterstützung wird aber in der Virtuellen Umgebung nicht geboten. Argumented Reality-Komponenten sind bisher nicht bekannt. In diesem Artikel werden nach einer Analyse der benötigten Technologien die Nutzenpotentiale insb. durch den Einsatz von AR ausgelotet.

Komponenten zur aktiven Unterstützung der Analyse von Materialflusssimulationen in virtuellen Umgebungen - Dangelmaier, Wilhelm; Franke, Werner; Mueck, Bengt; Fischer, Matthias (2. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung)
Simulation und Visualisierung sind anerkannte Mittel zum Verstehen und Analysieren von Fertigungsprozessen. In Visualisierungen von Fertigungsprozessen können Betrachter frei und ungeleitet umherwandern. Erkenntnisse werden so aber eher zufällig erworben. Dieser Artikel skizziert ein System und Methoden, die den Betrachter unterstützen auf auffällige/signifikante Prozesse/ Punkte in Materialflusssimulationen aufmerksam zu werden und diese zu entschärfen. Es wird der Entwurf eines Werkzeugs beschrieben, dass den Betrachter einer Simulation die Möglichkeit bietet, signifikante Produktionsprozesse interaktiv zu verbessern. Der Benutzer wird sich in einer virtuellen 3D-Umgebung (Walkthrough-System) bewegen können und automatisch ermittelte Indizien für signifikante Abläufe erhalten. Zugleich soll die Simulation signifikante Objekte genauer simulieren. Bekundet der Benutzer Interesse an einem signifikanten Prozess, wird er automatisch zu dem jeweiligen Ort geführt werden und dort durch Eingriffe in die Simulation die kritische Situation experimentell untersuchen können. Da der kritische Moment in der Vergangenheit liegt und somit vom Betrachter schon verpasst ist, wird es dem Betrachter möglich sein, die Simulation auf einen Zeitpunkt vor dem Eintreten zurück zu setzen. Die virtuelle Szene (3D-Grafik-Modelle) einer typischen dynamischen Simulationsumgebung ist in der Regel zu komplex, um sie in Echtzeit in einem Walkthrough-System zu visualisieren und darzustellen. Typischerweise werden Approximationsverfahren eingesetzt, um die Komplexität zu reduzieren und ein flüssiges Navigieren des Betrachters zu erlauben. Durch spezifische Simulations-Anforderungen ist bekannt, an welchen Objekten des Simulationsmodells Probleme auftreten; sie sind für den Betrachter wichtig. Die zugehörigen virtuellen 3D-Repräsentanten, können von den Approximationsalgorithmen mit einer besonders hohen Darstellungsqualität dargestellt werden und die übrigen Teile der virtuellen Szene entsprechend vernachlässigt werden. Solche Approximationsalgorithmen und Datenstrukturen nutzen die spezifischen Eigenschaften virtueller Simulationsumgebungen aus, um eine hohe Darstellungsqualität und Darstellungsperformance zu erreichen.

Planung von komplexen Fertigungssystemen durch Einsatz einer VR/AR-unterstützten Simulation - Fischer, Matthias; Grafe, Michael; Matysczok, Carsten; Schoo, Michael; Mueck, Bengt (2. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung)
In der heutigen Zeit operieren Unternehmen zunehmend in einem schwierigen Umfeld: Die Innovationsdynamik nimmt zu und die Produktlebenszyklen werden kürzer. Daraus resultieren hohe Anforderungen an die Planung von Fertigungssysteme. Um diesen Prozess zu unterstützen, sollen die Technologien Augmented Reality und Virtual Reality in einem integrierten System genutzt werden. Dieses System unterstützt den Anwender bei der Modellbildung, der Validierung des Simulationsmodells sowie der folgenden Optimierung des Fertigungssystems. Durch die Entwicklung geeigneter Kopplungs- bzw. Integrationsmechanismen wird eine durchgängige Nutzung der Technologien AR, VR und Simulation realisiert. Die Visualisierung der anfallenden 3D-Daten innerhalb der VR- und ARUmgebungen erfolgt mittels einer 3D-Renderinglibrary, die es durch den Einsatz von neuen entwickelten Verfahren ermöglicht, die verwendeten 3D-Modelle weitgehend automatisiert aus unternehmensinternen 3D-CAD-Modellen zu generieren.

Randomized Pursuit-Evasion in Graphs - Adler, Micah; Vöcking, Berthold; Sohler, Christian; Räcke, Harald; Sivadasan, Naveen (Combinatorics, Probability & Computing)

Property Testing and Geometry - Sohler, Christian

Sonderforschungsbereich 376 Massive Parallelität: Algorithmen – Entwurfsmethoden – Anwendungen (Massively Parallel Computing: Algorithms – Design Methods – Applications) - Meyer auf der Heide, Friedhelm (it - Information Technology)
Zusammenfassung Vernetzte Systeme sind zu unverzichtbaren Bestandteilen unseres Umfelds geworden, zum Beispiel als Höchstleistungsrechner, als Kommunikations- und Informationssysteme oder als Planungs- und Steuerungskomponenten von Transport- und Produktionssystemen. Die ständig wachsende Komplexität solcher Systeme stellt Informatiker und Ingenieure vor immer neue Herausforderungen. In diesem Beitrag beschreibe ich die Zielsetzungen und die Struktur des SFB 376 Massive Parallelität: Algorithmen – Entwurfsmethoden – Anwendungen. Als Beispiel für unsere Arbeiten beschreibe ich einen algorithmisch orientierten Forschungszweig, in dem wir, ausgehend von theoretischen Problemen über effiziente Simulationen zwischen parallelen Rechenmodellen, Methoden, Techniken und Implementierungen entwickelt haben, die zu produktnahen Prototypen für die Speichervirtualisierung in verteilten Datenservern führen.