Parallel algorithm for finding intersections of line segments in 3-D (Dmitry Vyukov)

The included source code implements a parallel search for intersections of input line segments within a 3-D space, as described in the included problem description text file. Three different methods of solution are initially considered. Complexity analysis and potential parallelization of the first two (brute force search, sweep-line algorithm) are considered and used to eliminate each from further consideration. The third method, Tree Decomposition, is chosen and explained in detail. The idea behind Tree Decomposition is to spatially divide the line segments into three classifications: left, right, and straddle, where the lines in the left and right portions are completely contained within a classification (and cannot intersect) and those in the straddle branch have endpoints in both left and right spaces. Each branch can be similarly divided using a plane that has not been used until the set of lines in a leaf node is small enough to compute possible intersections. There are 5 points within the algorithm that can be executed in parallel. The write-up describes the parallelization details of each. Cilk++ is used for implementing the parallelism. The code was intended for Linux OS and includes a makefile to build the application.
DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.

There are downloads available under the Creative Commons License license. Download Now

Include in RSS: 

For more complete information about compiler optimizations, see our Optimization Notice.