Delaunay triangulation in Parallel and Distributed Environment
Delaunay triangulation is one of the fundamental topics in the computational geometry and it is used in many areas, such as terrain modeling (GIS), scientific data visualization and interpolation, robotics, pattern recognition, meshing for finite element methods (FEM), natural sciences, computer graphics and multimedia, etc.
Modern computer architectures allow us to compute the Delaunay triangulation in E2 or E3 with
thousands of points by any sequential algorithm in a reasonable time. However, current applications often need
to work with data sets such that they cannot be computed in one piece because of the common memory size limitations
or their processing consumes too much time. In such cases, a parallel algorithm is useful and welcome.
Quite a big set of parallel algorithms exists, however, most of these parallel algorithms were designed in times
when parallel architectures, with hundreds of processors, dominated in the research area and thus they put stress
usually on the scalability rather than on the robustness and simplicity. For most applications, a less scalable but
easy to implement and stable algorithm is preferred to a more scalable but complex one.
The current situation on the hardware market supports this tendency; in the last few years, multiprocessors with
several processors and shared memory have come into the consideration due to their low prices; especially
two-processor workstations are now widely spread. Clusters of workstations are also available; especially
small clusters are very popular.
The main goal of this research is to design a robust and simple parallel algorithm suitable for these architectures.
We have chosen the method of the incremental insertion with local transformation as a base for our parallel algorithms
because this method is easy to implement and it is stable (it produces fine quality meshes, no matter which kind of
point distribution is used). As this method has rather a sequential character, no wonder that, as far as we know,
there is no existing parallel algorithm based on it. A parallelization is, therefore, a challenge for us.
People
Recent papers in this area
Note 1: to see details about the enlisted papers and/or to download them, please, visit the publications section.
Note 2: some papers may not be included in the following list, please, visit the publication section to see the list of our papers.
- Kohout J, Kolingerová I. ACUT: Out-of-core Delaunay triangulation of large terrain data sets. To appear in: Proceedings in Vision, Modelling and Visualization (VMV 2007), November 7-9, 2007, Saarbrücken, Germany - will be published as Lecture Notes in Computer Science 2006, Springer-Verlag Heidelberg.
- Kohout J, Kolingerová I. Distributed dynamic terrain modeling of large data sets. In: Proceedings of 4th ISPRS Workshop on Dynamic and Multi-dimensional GIS (DMGIS 2005), September 5-8 2005, Pontypridd,UK, p. 73-78
- Kohout J, Kolingerová I, ®ára J. Parallel Delaunay triangulation in E2 and E3 for computers with shared memory. Parallel Computing 2005, Elsevier, North-Holland; 31(5):491-522
- Kohout J, Kolingerová I, ®ára J. Practically oriented parallel Delaunay triangulation in E2 for computers with shared memory. Computer & Graphics 2004, Elsevier, Pergamon Press; 28(5): 703-718
- Kohout J, Kolingerová I. Parallel Delaunay triangulation in E3: Make it simple. The Visual Computer 2003, Springer-Verlag Heidelberg; 19(7&8): 532-548
- Kohout J, Kolingerová I. Parallel Delaunay Triangulation based on Circum-Circle Criterion. In: Proceedings of SCCG 2003, Comenius University, April 24-26 2003, Budmerice, Slovakia. p. 85-93; published also in ACM Publishing House, NY, ISBN 1-58113-861-X
Current results
We have developped several parallel methods for the construction of the Delaunay triangulation based on randomized
incremental insertion with local improvements. We focused on two different goals. The first one was to speed-up the
computation of the Delaunay triangulation and, the second one, to process large data sets. In order to achieve the
first goal, we designed several methods for multiprocessors with shared memory and limited number of processors,
typically 2 or 4. The implementation of the developed methods is available as a part of the Modular Visualization
Environment [MVE] version 1.0; a software package that was developed at our institute.
According to our experiments, we found the methods almost insensitive to the point distribution of input data set.
They differ in the complexity of implementation, scalability and efficiency (considered for the optimal number of
processors). Batch method is limited to few processors only and usable in E2 only, however, it is very
efficient and simple to be implemented. Pessimistic method is the simplest method to be implemented but inefficient.
Optimistic method needs more complicated implementation but this method is efficient and scalable. Burglary method
is also complicated, however, very efficient in E2 (not that efficient in E3) and scalable.
Circum-circle method is very efficient in E2 when 2 threads are used.
Speed-up of the optimistic method in E2 for different types of data point distribution - Dell Power Edge 6400 (4 PEs).
For larger data sets, two different parallel algorithms suitable for clusters of workstations were implemented.
Although they are able to process data sets of theoretically unlimited sizes, in practice, we are limited to data sets
with several millions of points because the processing of larger data sets would consume too much time. The main
reason of huge time consumption is the inefficiency of algorithms caused by an
intensive network communication. Let us note that although the current solution is inefficient, the possibility to process
larger data sets itself is still a good result of our research. The largest data sets that we processed had 4M points in E2 and
1.4M points in E3.
In order to reduce the amount of network communication, we have recently (2007)
proposed a new method, called ACUT, that exploits a data stream approach combined together
with an incremental construction of convex hull to split points into domains
separated by Delaunay edges. These domains can be triangulated
simultaneously without communication (except for the initialization of
computation, indeed). At present, we have an out-of-core sequential version
of this method, i.e., domains are triangulated one after one.
The implementation was done in C++ and tested on generated data sets with
various point distributions: uniform, gauss, clusters
and for real data sets (mostly GTOPO30). The experiments proved
that the proposed approach is insensitive to point distributions and,moreover,
it can process data sets in almost linear time.
The runtime of ACUT for data sets with various
point distributions - Dell Optiplex GX620 (Intel Pentium Processor 3.2
GHz with Hyper-Threading Technology and EM64,
2GB Dual Channel DDR2 RAM, 250GB SATA disk).
A bottleneck is the construction of domains. It needs an unnecessarily large
amount of I/O operations, which has a negative influence on the efficiency
of algorithm. There are several options how to improve the
efficiency but these require further research. In our future research,
we also indend to employ more computers on the triangulation of domains
as well as on the construction of domains itself.
The profiling of ACUT for uniform data sets.
Available software
Demos
