StrSort Algorithms for Geometric Problems - Sohler, Christian; Lammersen, Christiane (Proceedings of the 23rd European Workshop on Computational Geometry (EWCG))
In the StrSort model [2], the input is given as a stream, e.g. a sequence of points, and an algorithm can perform (a) streaming and (b) sorting passes to process the stream. A streaming pass reads the input stream from left to right and writes an output stream, which is the input of the next pass. A sorting pass is a black box operation that sorts a stream according to some partial order. In this paper, we develop algorithms for two basic geometric problems in the StrSort model. At first, we propose a divide-and-conquer algorithm that computes the convex hull of a point set in 2D in O(log2 n) passes using O(1) memory. Then we give a StrSort algorithm to compute a (1+ε)-spanner for a point set in Rd for constant d and constant epsilon that uses O(logd-1 n) passes and O(log n) space. This result implies a (1+ε)-approximation of the Euclidean minimum spanning tree in Rd, for constant d and ε.

Testing Expansion in Bounded-Degree Graphs - Sohler, Christian; Czumaj, Artur (Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS))

Small Space Representations for Metric Min-Sum k-Clustering and their Applications - Sohler, Christian; Czumaj, Artur (Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS'07))

Sublinear-time approximation algorithms for clustering via random sampling - Sohler, Christian; Czumaj, Artur (Random Structures & Algorithms)
We present a novel analysis of a random sampling approach for four clustering problems in metric spaces: k-median, k-means, min-sum k-clustering, and balanced k-median. For all these problems, we consider the following simple sampling scheme: select a small sample set of input points uniformly at random and then run some approximation algorithm on this sample set to compute an approximation of the best possible clustering of this set. Our main technical contribution is a significantly strengthened analysis of the approximation guarantee by this scheme for the clustering problems.The main motivation behind our analyses was to design sublinear-time algorithms for clustering problems. Our second contribution is the development of new approximation algorithms for the aforementioned clustering problems. Using our random sampling approach, we obtain for these problems the first time approximation algorithms that have running time independent of the input size, and depending on k and the diameter of the metric space only. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007A preliminary extended abstract of this work appeared in Proceedings of the 31st Annual International Colloquium on Automata, Languages and Programming (ICALP), pp. 396407, 2004.

A PTAS for k-means clustering based on weak coresets - Sohler, Christian; Monemizahdeh, Morteza; Feldman, Dan (Proceedings of the 23rd annual symposium on computational geometry (SoCG'07))

Efficient kinetic data structures for MaxCut - Sohler, Christian; Czumaj, Artur; Frahling, Gereon (Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG))

Dynamic and redundant data placement - Brinkmann, André; Effert, Sascha; Meyer auf der Heide, Friedhelm; Scheideler, Christian (IEEE International Conference on Distributed Computing Systems (ICDCS))
We present a randomized block-level storage virtualization for arbitrary heterogeneous storage systems that can distribute data in a fair and redundant way and can adapt this distribution in an efficient way as storage devices enter or leave the system. More precisely, our virtualization strategies can distribute a set of data blocks among a set of storage devices of arbitrary non-uniform capacities so that a storage device representing x% of the capacity in the system will get x% of the data (as long as this is in principle possible) and the different copies of each data block are stored so that no two copies of a data block are located in the same device. Achieving these two properties is not easy, and no virtualization strategy has been presented so far that has been formally shown to satisfy fairness and redundancy while being time- and space-eflcient and allowing an efficient adaptation to a changing set of devices.

Smart Teams: Simulating Large Robotic Swarms in Vast Environments - Arens, Stephan; Buss, Alexander; Deck, Helena; Dynia, Miroslaw; Fischer, Matthias; Hagedorn, Holger; Isaak, Peter; Kutylowski, Jaroslaw; Meyer auf der Heide, Friedhelm; Nesterow, Viktor; Ogiermann, Adrian; Stobbe, Boris; et al. (Proceedings of the 4th International Symposium on Autonomous Minirobots for Research and Edutainment)
We consider the problem of exploring an unknown environment using a swarm of autonomous robots with collective behavior emerging from their local rules. Each robot has only a very restricted view on the environment which makes cooperation difficult. We introduce a software system which is capable of simulating a large number of such robots (e.g. 1000) on highly complex terrains with millions of obstacles. Its main purpose is to easily integrate and evaluate any kind of algorithm for controlling the robot behavior. The simulation may be observed in real-time via a visualization that displays both the individual and the collective progress of the robots. We present the system design, its main features and underlying concepts.

Local strategies for maintaining a chain of relay stations between an explorer and a base station - Dynia, Miroslaw; Kutylowski, Jaroslaw; Meyer auf der Heide, Friedhelm; Schrieb, Jonas (Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '07)

Efficient Collision Detection for Point and Polygon Based Models - Klein, Jan

Position-based Routing Strategies - Rührup, Stefan

Single-Minded Unlimited Supply Pricing on Sparse Instances - Briest, Patrick; Krysta, Piotr (Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA))

Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels - Briest, Patrick; Gunia, Christian (Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC))

Die Analyse von Estimation-of-Distribution-Algorithmen auf ausgewählten Funktionen - Degener, Bastian

Distributed random digraph transformations for peer-to-peer networks - Mahlmann, Peter; Schindelhauer, Christian (Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures - SPAA '06)
We study the problem of designing an adaptive hash table for redundant data storage in a system of storage devices with arbitrary capacities. Ideally, such a hash table should make sure that (a) a storage device with x% of the available capacity should get x% of the data, (b) the copies of each data item are distributed among the storage devices so that no two copies are stored at the same device, and (c) only a near-minimum amount of data replacements is necessary to preserve (a) and (b) under any change in the system. Hash tables satisfying (a) and (c) are already known, and it is not difficult to construct hash tables satisfying (a) and (b). However, no hash table is known so far that can satisfy all three properties as long as this is in principle possible. We present a strategy called SPREAD that solves this problem for the first time. As long as (a) and (b) can in principle be satisfied, SPREAD preserves (a) for every storage device nearly optimal, with high probability, guarantees (b) for every data item, and only needs a constant factor more data replacements than minimum possible in order to preserve (a) and (b).

Online Multi-path Routing in a Maze - Rührup, Stefan; Schindelhauer, Christian (Proc. of the 17th International Symposium on Algorithms and Computation (ISAAC 2006))

SAN Optimal Multi Parameter Access Scheme - Schindelhauer, Christian; Schomaker, Gunnar (5th International Conference on Networking (ICN))
Storage Area Networks commonly consist a more or less static set of n data servers that handle a dynamic collection of m documents. Such SANs can minimize the access time to documents by distributing each document among several servers, allowing users to access documents in parallel. This paper describes an efficient solution for providing parallel access to multiple hard disks for popular content. In extension to previous approaches we provide an efficient and elegant hash table data structure for utilizing the full capacity of each data server. Concerning the dynamics, documents as well as server may be added or removed from the system causing only local changes. We consider sequential and parallel access to data in the average case. For the average time model we present a fast optimal algorithm.

Improved Bounds for Online Multi-Path Routing in Faulty Mesh Networks - Rührup, Stefan; Schindelhauer, Christian

Predictive Replication and Placement Strategies for Movie Documents in heterogeneous Content Delivery Networks - Schomaker, Gunnar; Loeser, Christoph; Schubert, Matthias (5th International Conference on Networking (ICN).)
In previous publications there have been several proposals regarding replica generation and placement of movie content in content-distribution-networks or P2P overlays. Within this paper we extend approaches for heterogeneous placement scenarios described in prior publications. Therefor we presume heterogeneous server peers' bandwidth, HD capacity, and movie popularities. Movie documents are replicated and placed onto server peers with respect to the predicted popularity values. Thus each document aims to gain fair networks resources according to its popularity. We present simulation results of heuristics of different placement strategies and compare them with a near optimal technique.

Realizing Multilevel Snapshots in Dynamically Changing Virtualized Storage Environments - Brinkmann, Andre; Effert, Sascha; Heidebuer, Michael; Vodisek, Mario (5th International Conference on Networking (ICN))

Size equivalent cluster trees (SEC-Trees) realtime rendering of large industrial scenes - Kortenjan, Michael; Schomaker, Gunnar (4th International Conference on Virtual Reality, Computer Graphics, Visualization and Interaction (Afrigraph 2006))
#hniid 2484

Reliable Broadcasting Without Collision Detection - Kutyłowski, Jarosław; Zagórski, Filip (SOFSEM 2006: Theory and Practice of Computer Science)
We propose a dynamic, ad-hoc communication network consisting of mobile units that can warn about traffic jams on motorways. Our goal is to provide a practical, low cost solution. Therefore we consider very simple wireless communication hardware, without collision detection, with very small bandwidth and a probabilistic model of link failure. We provide a complete system architecture. For this purpose we design and analyze solutions for size approximation, leader election and broadcasting. Our algorithms are fine-tuned for fast operation in a practical setting. We provide both a theoretical and experimental evaluation of our solutions. Our contribution is much different from the previous work, where either pure theoretical models with a pure theoretical analysis are provided or algorithms working in practical models are evaluated only through simulations.

Influence of adaptive data layouts on performance in dynamically changing storage environments - Brinkmann, Andre; Effert, Sascha; Heidebuer, Michael; Vodisek, Mario (14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP'06))
For most of today's IT environments, the tremendous need for storage capacity in combination with a required minimum I/O performance has become highly critical. In dynamically growing environments, a storage management solution's underlying data distribution scheme has great impact to the overall system I/O performance. The evaluation of a number of open system storage visualization solutions and volume managers has shown that all of them lack the ability to automatically adapt to changing access patterns and storage infrastructures; many of them require an error prone manual re-layout of the data blocks, or rely on a very time consuming re-striping of all available data. This paper evaluates the performance of conventional data distribution approaches compared to the adaptive virtualization solution V:DRIVE in dynamically changing storage environments. Changes of the storage infrastructure are normally not considered in benchmark results, but can have a significant impact on storage performance. Using synthetic benchmarks, V:DRIVE is compared in such changing environments with the non-adaptive Linux logical volume manager (LVM). The performance results of our tests clearly outline the necessity of adaptive data distribution schemes.

Self-Coordinating Systems: The Next Challenge in Research on Distributed Systems
We present a parallel algorithm for the rendering of complex three-dimensional scenes. The algorithm runs across heterogeneous architectures of PC-clusters consisting of a visualization-node, equipped with a powerful graphics adapter, and cluster nodes requiring weaker graphics capabilities only. The visualization-node renders a mixture of scene objects and simplified meshes (Reliefboards). The cluster nodes assist the visualization-node by asynchronous computing of Reliefboards, which are used to replace and render distant parts of the scene. Our algorithm is capable of gaining significant speedups if the cluster's nodes provide weak graphics adapters only. We trade the number of cluster nodes off the scene objects' image quality.

New trends in parallel and distributed computing - Monien, Burkhard; Meyer auf der Heide, Friedhelm

Directional Communication in Mobile Ad Hoc Networks - Grünewald, Matthias; Meyer auf der Heide, Friedhelm; Rührup, Stefan; Schindelhauer, Christian; Volbert, Klaus (New Trends in Parallel & Distributed Computing, 6th Int. Heinz Nixdorf Symposium)

Computing Clustering Coefficients in Data Streams - Sohler, Christian; Frahling, Gereon; Marchetti-Spaccamela, Alberto; Leonardi, Stefano; Buriol, Luciana (Proceedings of the European Conference on Complex Systems (ECCS'06))
We present random sampling algorithms that with probability at least 1 - δ compute a (1 ± ǫ)- approximation of the clustering coefficient, the transitiv ity coefficient, and of the number of bipartite cliques in a graph given as a stream of edges. Our methods can be extended to approximately count the number of occurences of fixed constant-size subgraphs. Our a lgorithms only require one pass over the input stream and their storage space depends only on structural parameters of the graphs, the approxi- mation guarantee, and the confidence probability. For examp le, the algorithms to compute the clustering and transitivity coefficient depend on that coefficient but n ot on the size of the graph. Since many large social networks have small clustering and transitivity coe fficient, our algorithms use space independent of the size of the input for these graphs. We implemented our algorithms and evaluated their performance on networks from different appli- cation domains. The sizes of the considered input graphs varied from about 8, 000 nodes and 40, 000 edges to about 135 million nodes and more than 1 billion edges. For both algorithms we run experiments with a sample set size varying from 100, 000 to 1, 000, 000 to evaluate running time and approximation guarantee. Our algorithms appear to be time efficient for the se sample sizes.

Counting Triangles in Data Streams - Sohler, Christian; Frahling, Gereon; Marchetti-Spaccamela, Alberto; Leonardi, Stefano; Buriol, Luciana

A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem - Sohler, Christian; Gehweiler, Joachim; Lammersen, Christiane (Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA))
In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our distributed algorithm uses three communication rounds with message sizes bounded to O(log n) bits where n is the number of points. We also extend our algorithm to constant powers of metric spaces, where we also obtain a randomized constant factor approximation algorithm.

Power-Aware Collective Tree Exploration - Dynia, Miroslaw; Korzeniowski, Miroslaw; Schindelhauer, Christian (Architecture of Computing Systems - ARCS)

Average and Smoothed Complexity of Geometric Structures - Damerow, Valentina

A Web Computing Environment for Parallel Algorithms in Java - Bonorden, Olaf; Meyer auf der Heide, Friedhelm; Gehweiler, Joachim (Journal on Scalable Computing: Practice and Experience)
We present a web computing library (PUBWCL) in Java that allows to execute tightly coupled, massively parallel algorithms in the bulk-synchronous (BSP) style on PCs distributed over the internet whose owners are willing to donate their unused computation power. PUBWCL is realized as a peer-to-peer system and features migration and restoration of BSP processes executed on it. The use of Java guarantees a high level of security and makes PUBWCL platform- independent. In order to estimate the loss of efficiency inherent in such a Java-based system, we have compared it to our C-based PUB-Library. As the unused computation power of the participating PCs is unpredictable, we need novel strategies for load balancing that have no access to future changes of the computation power available for the application. We develop, analyze, and compare different load balancing strategies for PUBWCL. In order to handle the influence of the fluctuating available computation power, we classify the external work load. During our evaluation of the load balancing algorithms we simulated the external work load in order to have repeatable testing conditions. With the best performing load balancing strategy we could save 39% of the execution time on average and even up to 50% in particular cases, in our test environment.

Distributed Load Balancing in Heterogeneous Peer-to-Peer Networks for Web Computing Libraries - Gehweiler, Joachim; Schomaker, Gunnar (Proceeedings of 10th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications (DS-RT))
We present a novel architecture for distributed computing in a peer-to-peer network. In particular, we realize the Paderborn University BSP-based Web Computing Library (PUBWCL), which formerly used a centralized client-server architecture for scheduling and load balancing, as a pure peer-to-peer system. Using distributed heterogeneous hash tables (DHHT), our architecture features scheduling and load balancing of tightly coupled, massively parallel algorithms in the bulk-synchronous (BSP) style with a minimal number of migrations.

A combinatorial algorithm for weighted stable sets in bipartite graphs - Faigle, Ulrich; Frahling, Gereon (Discrete Applied Mathematics)
Computing a maximum weighted stable set in a bipartite graph is considered well-solved and usually approached with preflow-push, Ford–Fulkerson or network simplex algorithms. We present a combinatorial algorithm for the problem that is not based on flows. Numerical tests suggest that this algorithm performs quite well in practice and is competitive with flow based algorithms especially in the case of dense graphs.

A fast k-means implementation using coresets - Frahling, Gereon; Sohler, Christian (Proceedings of the twenty-second annual symposium on Computational geometry - SCG '06)
In this paper we develop an efficient implementation for a k-means clustering algorithm. Our algorithm is a variant of KMHybrid [28, 20], i.e. it uses a combination of Lloyd-steps and random swaps, but as a novel feature it uses coresets to speed up the algorithm. A coreset is a small weighted set of points that approximates the original point set with respect to the considered problem. The main strength of the algorithm is that it can quickly determine clusterings of the same point set for many values of k. This is necessary in many applications, since, typically, one does not know a good value for k in advance. Once we have clusterings for many different values of k we can determine a good choice of k using a quality measure of clusterings that is independent of k, for example the average silhouette coefficient. The average silhouette coefficient can be approximated using coresets.To evaluate the performance of our algorithm we compare it with algorithm KMHybrid [28] on typical 3D data sets for an image compression application and on artificially created instances. Our data sets consist of 300,000 to 4.9 million points. We show that our algorithm significantly outperforms KMHybrid on most of these input instances. Additionally, the quality of the solutions computed by our algorithm deviates less than that of KMHybrid.We also computed clusterings and approximate average silhouette coefficient for k=1,…,100 for our input instances and discuss the performance of our algorithm in detail.

Modeling and Investigation of Robot Swarms - Hamann, Heiko

Geometric spanners with applications in wireless networks - Schindelhauer, Christian; Volbert, Klaus; Ziegler, Martin (Computational Geometry)

Effectively open real functions - Ziegler, Martin (Journal of Complexity)

Uncomputability Below the Real Halting Problem - Meer, Klaus; Ziegler, Martin (Logical Approaches to Computational Barriers)

d³FACT insight goes parallel - Aggregation of multiple simulations - Dangelmaier, Wilhelm; Huber, Daniel; Laroque, Christoph; Aufenanger, Mark; Fischer, Matthias; Krokowski, Jens; Kortenjan, Michael (Simulation and Visualization 2006 (SimViS))
In this paper the ideas of a new research project are presented. The material flow simu- lator d3FACT insight shall manage multiple parallel and time synchronous simulations to grand the power of real-time visualization in combination with statistical analysis. This research is issued to overcome the conflict of simulation run repetition for a good statistical basis and real-time immersive visualization. A side effect will be the reduc- tion of time needed for simulation experiments. The planned simulation tool has the feature of triggered cloning, i.e., the user can decide during runtime to clone a set of simulations after changing parameters to preserve the original system. The simulations will be aggregated by visualization and statistics. The rendering is planned to overlay several simulations using effects like inking and transparency. Simulation data will be aggregated with statistical functions and diagrams.

Sublinear-time Algorithms - Sohler, Christian; Czumaj, Artur (EATCS Bulletin)

Efficient Parallel Algorithms - Bonorden, Olaf; Gehweiler, Joachim; Meyer auf der Heide, Friedhelm; Rehberg, Bettina (Proceedings of 6th International Heinz Nixdorf Symposium: New Trends in Parallel & Distributed Computing)

De Dictionariis Dynamicis Pauco Spatio Utentibus ({lat.} On Dynamic Dictionaries Using Little Space) - Demaine, Erik D.; Meyer auf der Heide, Friedhelm; Pagh, Rasmus; Pǎtraşcu, Mihai (LATIN 2006: Theoretical Informatics)

Smart Robot Teams Exploring Sparse Trees - Dynia, M.; Kutyłowski, J.; Meyer auf der Heide, Friedhelm; Schindelhauer, Christian (Lecture Notes in Computer Science)

Maintaining Communication Between an Explorer and a Base Station - Dynia, Miroslaw; Kutyłowski, Jarosław; Lorek, Paweł; Meyer auf der Heide, Friedhelm (IFIP International Federation for Information Processing)

SmartS Simulator Design - Dynia, Miroslaw; Kuhmlehn, Andreas; Kutylowski, Jaroslaw; Meyer auf der Heide, Friedhelm; Schindelhauer, Christian

Geometric Spanners for Topology Control in Wireless Networks - Volbert, Klaus

Peer-to-peer networks based on random transformations of connected regular undirected graphs - Mahlmann, Peter; Schindelhauer, Christian (Proceedings of the 17th annual ACM symposium on Parallelism in algorithms and architectures - SPAA'05)
We present k-Flipper, a graph transformation algorithm that transforms regular undirected graphs. Given a path of k+2 edges it interchanges the end vertices of the path. By definition this operation preserves regularity and connectivity. We show that every regular connected graph can be reached by a series of these operations for all k ¡Ý 1. We use a randomized version, called Random k-Flipper, in order to create random regular connected undirected graphs that may serve as a backbone for peer-to-peer networks. We prove for degree d¡Ê ¦¸(log n) that a series of O(dn) Random k-Flipper operations with k ∈ ¦¨(d2n2 log 1/¦Å) transforms any graph into an expander graph with high probability, i.e. 1-n-¦¨(1). The Random 1-Flipper is symmetric, i.e. the transformation probability from any labeled d-regular graph G to G' is equal to those from G' to G. From this and the reachability property we conclude that in the limit a series of Random 1-Flipper operations converges against an uniform probability distribution over all connected labeled d-regular graphs. For degree d ∈ ω(1) growing with the graph size this implies that iteratively applying Random 1-Flipper transforms any given graph into an expander asymptotically almost surely. We use these operations as a maintenance operation for a peer-to-peer network based on random regular connected graphs that provides high robustness and recovers from degenerate network structures by continuously applying these random graph transformations. For this, we describe how network operations for joining and leaving the network can be designed and how the concurrency of the graph transformations can be handled.

Competitive Time and Traffic Analysis of Position-Based Routing using a Cell Structure - Rührup, Stefan; Schindelhauer, Christian (19th IEEE International Parallel and Distributed Processing Symposium)
We present a strategy for organizing the communication in wireless ad hoc networks based on a cell structure. We use the unit disk graph model and assume positioning capabilities for all nodes. The cell structure is an abstract view on the network and represents regions where nodes reside (node cells), regions that can be used for the communication flow (link cells) and regions that cannot be bridged due to the restricted transmission range (barrier cells). Each node can establish a cell classification of its neighborhood based on the position data which is announced by all nodes. The cell structure has two advantages for applying position-based routing: It helps to determine local minima for greedy forwarding and improves recovery from such minima, because for recovery all edges can be used in contrast to other topology-based rules that can be appliedonly on a planar subgraph. For the analysis of position-based routing algorithms the measures time and traffic are based on the cell structure. The difficulty of exploring the network is expressed by the size of the barriers (i.e. the number of cells in the perimeters). Exploration can be done in parallel, but with increasing traffic. We propose a comparative measure to assess both time and traffic, the combined comparative ratio, which is the maximum of the ratio of routing time and optimal time and the ratio of the traffic and the minimum exploration costs. While flooding and common single-path strategies have a linear ratio, we present a simple algorithm that has a sub-linear combined comparative ratio of O(sqrt(h)), where h is the minimal hop distance between source and target.

Performance Analysis of the Hierarchical Layer Graph for Wireless Networks - Rührup, Stefan; Schindelhauer, Christian; Volbert, Klaus (Proc. of 4th International Conference on Ad-Hoc, Mobile & Wireless Networks (ADHOC-NOW 2005))
The Hierarchical Layer Graph (HL graph) is a promising network topology for wireless networks with variable transmission ranges. It was introduced and analyzed by Meyer auf der Heide et al. 2004. In this paper we present a distributed, localized and resource-efficient algorithm for constructing this graph. The qualtiy of the HL graph depends on the domination radius and the publication radius, which affect the amount of interference in the network. These parameters also determine whether the HL graph is a c-spanner, which implies an energy-efficient topology. We investigate the performance on randomly distributed node sets and show that the restrictions on these parameters derived from a worst case analysis are not so tight using realistic settings. Here, we present the results of our extensive experimental evaluation, measuring congestion, dilation and energy. Congestion includes the load that is induced by interfering edges. We distinguish between congestion and realistic congestion where we also take the signal-to-interference ratio into account. Our experiments show that the HL graph contains energy-efficient paths as well as paths with a few number of hops while preserving a low congestion.

Probability Distributions for Channel Utilisation - Schindelhauer, Christian; Voß, Kerstin (Proc. of 4th International Conference on Ad-Hoc Networks & Wireless (ADHOC-NOW 2005))

Towards Self-Organizing Query Routing and Processing for Peer-to-Peer Web Search - Schindelhauer, Christian; Weikum, Gerhard; Hales, David; Triantafillou, Peter (European Conference on Complex Systems (ECCS 2005))

Distributed MD - Brinkmann, André; Effert, Sascha; Heidebuer, Michael; Vodisek, Mario (In Proceedings of the International Workshop on Storage Network Architecture and Parallel I/Os)
Data has become the most valuable asset for many companies; loosing important data can cause companies to fail quite immediately. The protection of data inside storage systems is mostly achieved by using a RAID scheme that adds redundant data to user data, enabling recovery from single or multiple disk failures. This protection against data loss in case of a disk failure can be achieved either by dedicated hardware or a software RAID solution. One major advantage of software RAID is that it comes for free as a built-in functionality in many operating systems like Linux or Microsoft Windows. The drawback of the built-in functionality is that it is not suited to run in multiple server environments; synchronization and recovery processes can be corrupted if more than a single server is allowed to access a software RAID volume. In this paper, we present an enhancement for the Linux md-driver that enables a consistent usage of RAID in multiple server environments. Based on the V:DRIVE virtualization environment, RAID volumes can be consistently synchronized and recovered even in distributed environments. Besides the architectural concepts, we present measurements that indicate the viability of this enhanced, distributed version of md.

An integrated Architecture for Business Intelligence support from Application down to Storage - Brinkmann, André; Effert, Sascha; Heidebuer, Michael; Vodisek, Mario; Baars, Henning (In Proceedings of the International Workshop on Storage Network Architecture and Parallel I/Os)
Recent developments both in the business and the technological domain have led to a significant increase in demand for Business Intelligence (BI) infrastructures that can handle huge amounts of data in small time frames. BI applications are increasingly used by large user bases on all management levels; support tasks spanning the complete value chain are based on transactional data and are directly coupled with operational systems in closed loop approaches. To effectively handle the resulting data volume turns out to be an extremely challenging task which encompasses a variety of issues on different levels. We propose an integrated multi layer tool for monitoring, benchmarking, analyzing, and optimizing the performance of such BI infrastructures. Inside this paper we give a coarse outline of the tools architecture and demonstrate the value of distinct measurement points at operating system layer. For that purpose we introduce a kernel based benchmark environment and present first measurement results. The gathered data clearly indicates that a meaningful analysis of performance benchmarks without kernel trace points is of limited value - which shows the necessity to consider a separate component within the tools architecture.

The expected running time of hierarchical collision detection - Klein, Jan; Zachmann, Gabriel (ACM SIGGRAPH 2005 Posters on - SIGGRAPH '05)

Interpolation Search for Point Cloud Intersection - Klein, Jan; Zachmann, Gabriel (Proceedings of the 13-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision'2005 (WSCG'2005))

Content Distribution in Heterogenous Video-on-Demand P2P Networks with ARIMA Forecasts - Loeser, Chris; Schomaker, Gunnar; Brinkmann, André; Vodisek, Mario; Heidebuer, Michael (Proceedings of the 4th International Conference on Networking)

Nonlinear Reformulation of Heisenberg's Dynamics - Ziegler, Martin; Fuchssteiner, Benno (International Journal of Theoretical Physics)

Weighted distributed hash tables - Schindelhauer, Christian; Schomaker, Gunnar (SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Las Vegas, Nevada, USA)

Online Routing in Faulty Meshes with Sub-linear Comparative Time and Traffic Ratio - Rührup, Stefan; Schindelhauer, Christian (Algorithms – ESA 2005)

Design, analysis, and evaluation of a data structure for distributed virtual environments - Fischer, Matthias

Virtual and augmented reality support for discrete manufacturing system simulation - Dangelmaier, Wilhelm; Fischer, Matthias; Gausemeier, Jürgen; Grafe, Michael; Matysczok, Carsten; Mueck, Bengt (Computers in Industry)
Nowadays companies operate in a difficult environment: the dynamics of innovations increase and product life cycles become shorter. Furthermore products and the corresponding manufacturing processes get more and more complex. Therefore, companies need new methods for the planning of manufacturing systems. One promising approach in this context is digital factory/virtual productionthe modeling and analysis of computer models of the planned factory with the objective to reduce time and costs. For the modeling and analysis various simulation methods and programs have been developed. They are a highly valuable support for planning and visualizing the manufacturing system. But there is one major disadvantage: only experienced and long trained experts are able to operate with these programs. The graphical user interface is very complex and not intuitive to use. This results in an extensive and error-prone modeling of complex simulation models and a time-consuming interpretation of the simulation results. To overcome these weak points, intuitive and understandable manmachine interfaces like augmented and virtual reality can be used. This paper describes the architecture of a system which uses the technologies of augmented and virtual reality to support the planning process of complex manufacturing systems. The proposed system assists the user in modeling, the validation of the simulation model, and the subsequent optimization of the production system. A general application of the VR- and AR-technologies and of the simulation is realized by the development of appropriate linking and integration mechanisms. For the visualization of the arising 3D-data within the VR- and AR-environments, a dedicated 3D-rendering library is used.

Multi-User Support and Motion Planning of Humans and Humans Driven Vehicles in Interactive 3D Material Flow Simulations - Fischer, Matthias; Mueck, B.; Mahajan, K.; Kortenjan, M.; Laroque, C.; Dangelmaier, W. (Proceedings of the Winter Simulation Conference)

Abstract Combinatorial Programs and Efficient Property Testers - Czumaj, Artur; Sohler, Christian (SIAM Journal on Computing)
Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs . We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension , then the property has an efficient tester. We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversal distance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties.

Facility Location in Sublinear Time - Bădoiu, Mihai; Czumaj, Artur; Indyk, Piotr; Sohler, Christian (Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP))

Coresets in Dynamic Geometric Data Streams - Sohler, Christian; Frahling, Gereon (Proceedings of the 37th ACM Symposium on Theory of Computing (STOC))
A dynamic geometric data stream consists of a sequence of m insert/delete operations of points from the discrete space {1,..., ∆} d [26]. We develop streaming (1 + ɛ)-approximation algorithms for k-median, k-means, MaxCut, maximum weighted matching (MaxWM), maximum travelling salesperson (MaxTSP), maximum spanning tree (MaxST), and average distance over dynamic geometric data streams. Our algorithms maintain a small weighted set of points (a coreset) that approximates with probability 2/3 the current point set with respect to the considered problem during the m insert/delete operations of the data stream. They use poly(ɛ −1, log m, log ∆) space and update time per insert/delete operation for constant k and dimension d. Having a coreset one only needs a fast approximation algorithm for the weighted problem to compute a solution quickly. In fact, even an exponential algorithm is sometimes feasible as its running time may still be polynomial in n. For example one can compute in poly(log n, exp(O((1+log(1/ɛ)/ɛ) d−1))) time a solution to k-median and k-means [21] where n is the size of the current point set and k and d are constants. Finding an implicit solution to MaxCut can be done in poly(log n, exp((1/ɛ) O(1))) time. For MaxST and average distance we require poly(log n, ɛ −1) time and for MaxWM we require O(n 3) time to do this.

Testing hypergraph colorability - Czumaj, Artur; Sohler, Christian (Theoretical Computer Science)

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time - Czumaj, Artur; Ergün, Funda; Fortnow, Lance; Magen, Avner; Newman, Ilan; Rubinfeld, Ronitt; Sohler, Christian (SIAM Journal on Computing)
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in $\mathbb R^d$. We focus on the setting where 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 + \eps$ using only $\widetilde{\O}(\sqrt{n} \, \text{poly} (1/\eps))$ 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 neighbor queries. Read More: https://epubs.siam.org/doi/10.1137/S0097539703435297

Online Occlusion Culling - Frahling, Gereon; Krokowski, Jens (Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005))
Modern computer graphics systems are able to render sophisticated 3D szenes consisting of millions of polygons. In this paper we address the problem of occlusion culling. Aila, Miettinen, and Nordlund suggested to implement a FIFO buffer on graphics cards which is able to delay the polygons before drawing them. When one of the polygons within the buffer is occluded or masked by another polygon arriving later from the application, the rendering engine can drop the occluded one without rendering, saving important rendering time. We introduce a theoretical online model to analyse these problems in theory using competitive analysis. For different cost measures addressed we invent the first competitive algorithms for online occlusion culling. Our implementation shows that these algorithms outperform known ones for real 3D scenes as well.

Dynamic Page Migration Under Brownian Motion - Bienkowski, Marcin; Korzeniowski, Miroslaw (Proc. of the European Conference in Parallel Processing (Euro-Par))
We consider Dynamic Page Migration (DPM) problem, one of the fundamental subproblems of data management in dynamically changing networks. We investigate a hybrid scenario, where access patterns to the shared object are dictated by an adversary, and each processor performs a random walk in X. We extend the previous results of [4]: we develop algorithms for the case where X is a ring, and prove that with high probability they achieve a competitive ratio of O~(min{D−−√4,n}), where D is the size of the shared object and n is the number of nodes in the network. These results hold also for any d-dimensional torus or mesh with diameter at least Ω~(D−−√).

Bucket Game with Applications to Set Multicover and Dynamic Page Migration - Bienkowski, Marcin; Byrka, Jarosław (Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005))
We present a simple two-person Bucket Game, based on throwing balls into buckets, and we discuss possible players' strategies. We use these strategies to create an approximation algorithm for a generalization of the well known Set Cover problem, where we need to cover each element by at least $k$ sets. Furthermore, we apply these strategies to construct a randomized algorithm for Dynamic Page Migration problem achieving the optimal competitive ratio against an oblivious adversary.

Dynamic Page Migration with Stochastic Requests - Bienkowski, Marcin (Proc. of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005))
The page migration problem is one of subproblems of data management in networks. It occurs in a distributed network of processors sharing one indivisible memory page of size D. During runtime, the processors access a unit of data from the page, and the system is allowed to migrate the page between the processors. The problem is to compute (on-line) a schedule of page movements to minimize the total communication cost. The Dynamic Page Migration problem is an extension to the page migration. It attempts to model the network dynamics, occurring, for example, in mobile networks. However, the pace of changes is restricted, i.e. the distances between processors can change only by a constant per round. The movement of the nodes induce changes in the communication cost between each pair of nodes, which is proportional to the distance between them raised to some power $alpha$. This is typical for mobile wireless networks, where nodes can move with a constant speed, and the cost of communication is measured in terms of energy used for sending the data. Thus, by setting $alpha$ equal to the propagation exponent of the medium, cost minimization becomes minimizing the total energy consumption in the system. However, as proven in citedynamic-page-migration, if both network mobility and request sequence are created by an adversary, then the competitive ratio is polynomially large in D and in the number of the nodes. In our search for a reasonable, close-to-reality model, in this paper we consider a scenario in which the network mobility is adversarial, but the requests are generated randomly by a stochastic process. We design an algorithm MTFR for this scenario, and prove that it is O(1)-competitive, on expectation and with high probability.

Cube Connected Cycles Based Bluetooth Scatternet Formation - Bienkowski, Marcin; Brinkmann, André; Korzeniowski, Miroslaw; Orhan, Orhan (Proceedings of the 4th International Conference on Networking)
Bluetooth is a wireless communication standard developed for personal area networks (PAN) that gained popularity in the last years. It was designed to connect a few devices together, however nowadays there is a need to build larger networks. Construction and maintenance algorithms have great effect on performance of the network. We present an algorithm based on Cube Connected Cycles (CCC) topology and show how to maintain the network so that it is easily scalable. Our design guarantees good properties such as constant degree and logarithmic dilation. Besides, the construction costs are proven to be at most constant times larger than any other algorithm would need.

Improved Algorithms for Dynamic Page Migration - Bienkowski, Marcin; Dynia, Miroslaw; Korzeniowski, Miroslaw (Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS))
The dynamic page migration problem citedynamic-page-migration is defined in a distributed network of $n$ mobile nodes sharing one indivisible memory page of size $D$. During runtime, the nodes can both access a unit of data from the page and move with a constant speed, thus changing the costs of communication. The problem is to compute online a schedule of page movements to minimize the total communication cost. In this paper we construct and analyze the first deterministic algorithm for this problem. We prove that it achieves an (up to a constant factor) optimal competitive ratio $O(n cdot sqrtD)$. We show that the randomization of this algorithm improves this ratio to $O(sqrtD cdot log n)$ (against an oblivious adversary). This substantially improves an $O(n cdot sqrtD)$ upper bound from citedynamic-page-migration. We also give an almost matching lower bound of $Omega(sqrtD cdot sqrtlog n)$ for this problem.

Data Management and Routing in General Networks - Räcke, Harald

Sampling in dynamic data streams and applications - Frahling, Gereon; Indyk, Piotr; Sohler, Christian (Proceedings of the twenty-first annual symposium on Computational geometry - SCG '05)
A dynamic geometric data stream is a sequence of m Add/Remove operations of points from a discrete geometric space (1,...,Δ)d [21]. Add(p) inserts a point p from (1,...,Δ)d into the current point set, Remove(p) deletes p from P. We develop low-storage data structures to (i) maintain ε-approximations of range spaces of P with constant VC-dimension and (ii) maintain an ε-approximation of the weight of the Euclidean minimum spanning tree of P. Our data structures use O(log3ε • log3(1/ε) • log(1/ε)/ε2) and O(log (1/δ) • (log Δ/ε)O(d)) bits of memory, respectively (we assume that the dimension d is a constant), and they are correct with probability 1-δ. These results are based on a new data structure that maintains a set of elements chosen (almost) uniformly at random from P.

On Approximating Real-World Halting Problems - Köhler, Sven; Schindelhauer, Christian; Ziegler, Martin (Fundamentals of Computation Theory)

An Explicit Solution to Post’s Problem over the Reals - Meer, Klaus; Ziegler, Martin (Fundamentals of Computation Theory)

Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism - Ziegler, Martin (Proc. CiE 2005: New Computational Paradigms)
The sometimes so-called Main Theorem of Recursive Analysis implies that any computable real function is necessarily continuous. We consider three relaxations of this common notion of real computability for the purpose of treating also discontinuous functions f:R->R: *) non-deterministic computation; *) relativized computation, specifically given access to oracles like 0' or 0''; *) encoding input x and/or output y=f(x) in weaker ways according to the Real Arithmetic Hierarchy. It turns out that, among these approaches, only the first one provides the required power.

Computational Power of Infinite Quantum Parallelism - Ziegler, Martin (International Journal of Theoretical Physics)

Methods to lead the user to significant processes in a 3D material flow simulation - Dangelmaier, Wilhelm; Mueck, Bengt; Fischer, Matthias; Mahajan, Kiran; Laroque, Christoph (Simulation in wider Europe - 19th European Conference on Modelling and Simulation ECMS 2005)

Glaschick, Rainer: Integrative Approach of Web Services and Universal Plug and Play within an AV Scenario - Loeser, Christoph; Drüke, Isabell; Oesterdiekhoff, Brigitte (IEEE International Conference on Industrial Informatics (INDIN))

Glaschick, Rainer; Service Oriented Interface Design for Embedded Devices - Oesterdiekhoff, Brigitte (IEEE International Conference on Emerging Technologies and Factory Automation (ETFA))

Dynamic Load Balancing in Distributed Hash Tables - Bienkowski, Marcin; Korzeniowski, Miroslaw; Meyer auf der Heide, Friedhelm (Peer-to-Peer Systems IV)

Page Migration in Dynamic Networks - Bienkowski, Marcin; Meyer auf der Heide, Friedhelm (Mathematical Foundations of Computer Science 2005)

A Web Computing Environment for Parallel Algorithms in Java - Bonorden, Olaf; Gehweiler, Joachim; Meyer auf der Heide, Friedhelm (Proceeedings of 6th International Conference on Parallel Processing and Applied Mathematics (PPAM))
We present a web computing library (PUBWCL) in Java that allows to execute strongly coupled, massively parallel algorithms in the bulk-synchronous (BSP) style on PCs distributed over the internet whose owners are willing to donate their unused computation power. PUBWCL is realized as a peer-to-peer system and features migration and restoration of BSP processes executed on it. The use of Java guarantees a high level of security and makes PUBWCL platform independent. In order to estimate the loss of efficiency inherent in such a Java-based system, we have compared it to our C-based PUB-Library.

Load Balancing Strategies in a Web Computing Environment - Bonorden, Olaf; Gehweiler, Joachim; Meyer auf der Heide, Friedhelm (Proceeedings of 6th International Conference on Parallel Processing and Applied Mathematics (PPAM))
We compare different load balancing strategies for Bulk-Synchronous Parallel (BSP) programs in a web computing environment. In order to handle the influence of the fluctuating available computation power, we classify the external work load. We evaluate the load balancing algorithms using our web computing library for BSP programs in Java (PUBWCL). Thereby we simulated the external work load in order to have repeatable testing conditions. With the best performing load balancing strategy we could save 39% of the execution time averaged and even up to 50% in particular cases.

Average case complexity of Voronoi diagrams of n sites from the unit cube - Bienkowski, Marcin; Damerow, Valentina; Meyer auf der Heide, Friedhelm; Sohler, Christian (Proceedings of the 21st European Workshop on Computational Geometry, Eindhoven, The Netherlands, March 9-11, 2005)

Abstracts Collection -- Algorithmic Aspects of Large and Complex Networks

Stability versus speed in a computable algebraic model - Ziegler, Martin (Theoretical Computer Science)

Data Distribution Algorithms for Storage Networks - Salzwedel, Kay

The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes - Briest, Patrick; Brockhoff, Dimo; Degener, Bastian; Englert, Matthias; Gunia, Christian; Heering, Oliver; Jansen, Thomas; Leifhelm, Michael; Plociennik, Kai; Röglin, Heiko; Schweer, Andrea; Sudholt, Dirk; et al. (Parallel Problem Solving from Nature - PPSN VIII)

Experimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatorial Optimization - Schweer, Andrea; Leifhelm, Michael; Degener, Bastian; Heering, Oliver; Tannenbaum, Stefan; Röglin, Heiko; Gunia, Christian; Englert, Matthias; Briest, Patrick; Sudholt, Dirk; Brockhoff, Dimo; Wegener, Ingo; et al. (Parallel Problem Solving from Nature - PPSN VIII)

A case for virtualized arrays of RAID - Brinkmann, André; Salzwedel, Kay; Vodisek, Mario (Proceedings of the international workshop on Storage network architecture and parallel I/Os - SNAPI '04)
Redundant arrays of independent disks, also called RAID arrays, have gained a wide popularity in the last twenty years. Most of the disks used in the server market are currently based on RAID technology. The primary reason for introducing RAID technology in 1988 has been the fact that large disk systems have become much slower and more expensive than the connection of a large number of inexpensive disks and the use of them as an array. The times seem to repeat themselves. Today, large scale RAID arrays have become incredible big and expensive. It seems that it makes sense to replace them by a collection of smaller and inexpensive arrays of JBODs or mid-ranged RAID arrays. In this paper we will show that combining these systems with state-of-the-art virtualization technology can lead to a system that is faster and less expensive than an enterprise storage system, while being as easy to manage and as reliable. Therefore we will outline the most important features of storage management and compare there realization in enterprise class storage systems and in current and future virtualization environments.

The design of PaMaNet the Paderborn mobile ad-hoc network - Schindelhauer, Christian; Böttcher, Stefan; Rammig, Franz (Proceedings of the second international workshop on Mobility management & wireless access protocols)
Wireless connectivity is state of the art for local area networks. Currently, most W-LAN networks rely on a centralized design with access points routing all inner and outbound traffic. These access points are intrinsic communication bottlenecks. Mobile Ad Hoc Networks (MANET) overcome this problem, because every participant works as well as a simple node and as a router. Current MANETs are restricted in scalability, because they rely on flooding mechanisms or complete routing tables. Other approaches, providing better scalability use clustering, yet network performance deteriorates in case of high node mobility. We describe the design of a PAMANET, the Paderborn Mobile Ad Hoc Network, a MANET overcoming these problems providing scalability and reliability in a mobile scenario. When implemented, PAMANET works with standard W-LAN IEEE 802.11 radio devices, provides IPv6 communication interfaces and works on personal computers under a standard Linux distribution. First, we present current routing protocols and classify them with respect to scalability and stability in dynamically evolving MANETs. Then, we discuss related research in the area of distributed hash tables and consistent hashing, used for relieving hot spots in the Web, storage area networks and peerto-peer networks, which inspires the design of PAMANET. PAMANET consists of three main components: First, the embedding of the routing layer into IEEE 802.11 and IPv6 by using techniques used at the ad hoc support library (aslib) by Gupta et al. Second, the routing layer which combines a landmark routing, hierarchical clustering, consistent hashing for providing location dependent addresses and lookup-service for the location of nodes. Third, a peerto-peer data storage system based on egoistic distributed caches enabling hop and traffic efficient data access on replicated data partitions. The routing layer incorporates a variety of new approaches. Link distances reflect the failure probability of links, which is estimated by the reciprocal age of the link. Then, we combine a landmarking system on this metric with the hierarchical layer graph yielding small landmark addresses and small routing tables. To balance the load of the distributed lookup-service for landmark addresses, a hierarchical weighted consistent hashing scheme is used. This ensures that each node receives an equal part of all landmark addresses. Using these mechanisms (regularly and on demand) PAMANET adjusts IPv6 routing tables such that short stable routes are preferred. For the distribution of control data like landmark information PAMANET uses a message box system interface to provide fast one-hop communication. On top of this system, PAMANET provides a peer-to-peer data storage and lookup system that realizes time, traffic, and load efficient access using egoistic caches and data segmentation strategies.

Virtualization with prefetching abilities based on iSCSI - Bleckmann, Peter; Schomaker, Gunnar; Slowik, Adrian (Proceeding of International Workshop on Storage Network Architecture and Parallel I/O)
The Internet-SCSI protocol [iSCSI] allows a client to interact with a remote SCSI-capable target by means of block-oriented commands encapsulated within TCP/IP packets. Thereby, iSCSI greatly simplifies storage virtualization, since clients can access storage in a unified manner, no matter whether the I/O-path is short or long distance. Intermediate devices located on the path between a client and a target can easily intercept iSCSI sessions and rewrite packets for the sake of load balancing, prefetching, or redundancy, to mention just a few beneficial applications. Within this paper we describe the design and implementation of such an iSCSI capable intermediate device that deploys prefetching strategies in combination with redundant disks to reduce average I/O-latency. Depending on its location within the network, this virtualization and prefetching device can hide wide area access latency and reduce network contention targeting remote SCSI-devices to a large extent.

Point Cloud Surfaces using Geometric Proximity Graphs - Klein, Jan; Zachmann, Gabriel (Computers and Graphics)

Proximity Graphs for Defining Surfaces over Point Clouds - Klein, Jan; Zachmann, Gabriel (Eurographics Symposium on Point-Based Grahics (SPBG'04))

Nice and Fast Implicit Surfaces over Noisy Point Clouds - Klein, Jan; Zachmann, Gabriel (SIGGRAPH 2004, Sketches)

Point Cloud Collision Detection - Klein, Jan; Zachmann, Gabriel (Computer Graphics Forum (Proceedings of EUROGRAPHICS 2004))