Intel® Developer Zone:
Courseware - Geometric Algorithms

  • Line segments: properties, intersections
  • Convex hull finding algorithms
  • Parallel algorithm for finding intersections of line segments in 3-D (Akki)
  • Material Type:

    Coding example, Problem set

    ISN Logo

    Technical Format:

    zip archive, PDF document, text file

    Location:

    Go to materials

    Date Added:

    03/22/2010

    Date Modified:

    03/22/2010

    Author

    Akshay Singh, Intel
    Description:

    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. The parallel algorithm divides the input line segments into a number of divisions based on the coordinates of the endpoints. In this way, processing can be more localized and not all possible pairs of intersecting lines would be considered. The division and comparison algorithm results in 184 independent tasks that can be assigned to thread through a thread pool model. Criteria for the categorization of lines, how to compute whether or not two given line segments intersect, and hints on ordering of tasks for better parallel performance are all included in the write-up. POSIX Threads 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.

    Recommended Audience:

    Advanced programmers, Undergraduate students

    Language:

    English

    Keywords:

    C++, POSIX Threads, Pthreads, Thread pool, computational geometry
  • Parallel algorithm for finding intersections of line segments in 3-D (Bradley Kuszmaul)
  • Material Type:

    Lecture / Presentation, Coding example, Problem set

    ISN Logo

    Technical Format:

    text file, zip archive, PDF document

    Location:

    Go to materials

    Date Added:

    03/17/2010

    Date Modified:

    03/17/2010

    Author

    Bradley Kuszmaul, MIT Computer Science and Artificial Intelligence Laboratory
    Description:

    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.

    Recommended Audience:

    Advanced programmers, Undergraduate students

    Language:

    English

    Keywords:

    3D Line segment, line intersection, Cilk++, tree decomposition, parallel merge sort, computational geometry, Intel Threading Challenge
  • Parallel algorithm for finding intersections of line segments in 3-D (Dmitry Vyukov)
  • Material Type:

    Lecture / Presentation, Coding example, Problem set

    ISN Logo

    Technical Format:

    text file, Word document, zip archive

    Location:

    Go to materials

    Date Added:

    03/17/2010

    Date Modified:

    03/17/2010

    Author

    Dmitry Vyukov, Intel Threading Challenge
    Description:

    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.

    Recommended Audience:

    Advanced programmers, Undergraduate students

    Language:

    English

    Keywords:

    3D Line segment, line intersection, Intel Threading Building Blocks, TBB, SSE, Streaming SIMD Execution, parallelsort algorithm, computational geometry
  • Parallel algorithm to 3-D Convex Hull Problem (Bradley Kuszmaul)
  • Material Type:

    Coding example, Problem set, Lecture / Presentation

    ISN Logo

    Technical Format:

    text file, zip archive, PDF document

    Location:

    Go to materials

    Date Added:

    03/17/2010

    Date Modified:

    03/17/2010

    Author

    Bradley Kuszmaul, Intel
    Description:

    The included code and white paper provides a parallel solution for the 3-D Convex Hull problem, as described in the included problem description text file. Parallelism is achieved using Cilk++. Possible points for the convex hull are found by repeatedly selecting four points from the input set and finding the largest volumes of the formed tetrahedrons (using matrix determinants). An O(n^4) algorithm confirms those points that are actually on the convex hull from the possible points previously found.
    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.

    Recommended Audience:

    Advanced programmers, Undergraduate students

    Language:

    English

    Keywords:

    C, Cilk++, computational geometry, C++, Convex Hull, 3D Convex Hull, Threading Challenge Contest, matrix determinant, tetrahedron volume