Parallel Convex Hull Construction using DAJ

Problem

For a description of the problem and of the algorithm used to solve it, see the slides I used in a presentation in the Parallel Computation Seminar: ch.ps.gz

Example

Press on the button to try the algorithm using 4 by 4 nodes to solve a problem with of 60 points. The window showing the solution will not be removed automatically. On some systems the window showing the results will not pop up.

Please enable Java

Screen shots

If you can not run the program directly, here are some screen shots. The screen shots show one window, where you can see the activity of the nodes and which channels are active. The second window shows the computed solution.

4 by 4 nodes, 60 points. Screen shots were taken after termination.
10 by 10 nodes, 250 points. The snapshot of the window showing the nodes was taken during the computation. You can see that some rows have already terminated while others are still working.

Source Files / Download

This is not an example of good Java programming style.

ConvexHull.jar. Java archive.
ConvexHull.tar.gz. Unix archive. Contains also the source files.
The individual source files: ConvexHull.java, IntMessage.java, Position.java, ConvexHullNode.java, Point.java, PositionMessage.java, PointSet.java, PositionSet.java, DrawWindow.java, PointsMessage.java

References

DAJ -- A Toolkit for the Simulation of Distributed Algorithms in Java
Selim G. Akl
The Design and Analysis of Parallel Algorithms
1989, Prentice-Hall Internationall, Inc. New Jersey
ISBN 0-13-200073-3

by Harald Deischinger
last updated: July 1st 1998