This is an implementation of the parallel dynamic well-spaced point set algorithm which is described in our SPAA 2011 paper. The well-spaced point set problem is, given a set of input points, to find a superset for which the Voronoi cell around each point has radius no greater than ρ times the distance to the point's nearest neighbor, for a parameter ρ>1. This is accomplished by inserting some number of Steiner points into the input point set. In our SOCG 2010 paper, we describe a method by which this problem may be solved dynamically, permitting a well-spaced superset to be calculated first of some initial point set, and then quickly updated when new points are inserted into, or old points removed from, the input set. In our SPAA 2011 paper, we show that this dynamic algorithm can be easily modified (conceptually, at least) to permit parallelization, permitting the work involved with updating the well-spaced superset to be distributed amongst some number of threads.
The conceptual appeal of this approach stems from the fact that both dynamization and parallelization depend on being able to identify independent parts of a computation. In ths case of dynamization, this information is used to ensure that only those portions of the computation the results of which could change will be recalculated. In the case of parallelization, the information is used to execute independent operations in parallel. The practical appeal stems from the fact that dynamization results in the greatest performance increase for small, localized changes, while parallelization improves performance most for large, unlocalized changes. Hence, while both problems may be solved using similar approaches, they address nearly-orthogonal domains.
The implementation is in C/C++. Only Linux is supported (and only 64-bit Ubuntu has been tested). In order to compile the C library interface and example programs, you'll require the boost, GMP and (optionally) libply libraries.
All source code is copyrighted, and licensed under the GPLv3.
TAR.GZ ZIP Source code dynamic_wsp_src.tgz (87K) dynamic_wsp_src.zip (102K)
When you untar (or unzip) the archive file, it will create two directories: lib and bin. These contain the C library interface and example programs, respectively.
The upper-level directory contains a Makefile, which you might need to modify. The "SUBDIRS" variable lists the subdirectories to build. You'll always want to build the C library ("lib"), but may omit the example programs ("bin") if you want to remove the dependency on the libply library. The only other important variable defined in the Makefile is "MAXIMUM_THREADS", which determines the maximum number of threads which may be used during a call to DynamicWSP_Refine(). Increasing the value of this variable will increase the memory usage of the library, so it would be advisable to leave it at its default value of 4 unless you are running on a machine with more than 4 cores, and empirically observe a significant speedup from the use of the extra cores. Once you're done editing the Makefile, simply run "make" in the upper-level directory.
The C library interface will be contained in the files "lib/libdynamic_wsp.a", which you should copy into a library directory (say "/usr/local/lib") and "lib/dynamic_wsp.h", which you should copy into an include directory (say "/usr/local/include").
I'm not going to give a detailed walkthrough of using the C library interface. The header file dynamic_wsp.h is well-commented, and should be self-explanatory, in the context of the above-cited papers.