Flip to Regular Triangulation and Convex Hull.

Area of Science:

• Computational Geometry
• Computer Graphics
• Parallel Computing

Background:

• Triangulation and convex hull construction are fundamental in computational geometry.
• Traditional flip algorithms are often sequential and difficult to parallelize.
• Graphics Processing Units (GPUs) offer massive parallelism suitable for geometric algorithms.

Purpose of the Study:

• To develop provably correct, order-flexible flip algorithms for 2D and 3D triangulations and convex hulls.
• To adapt these algorithms for efficient execution on parallel hardware, specifically GPUs.
• To demonstrate the performance benefits of parallel flip algorithms over sequential implementations.

Main Methods:

• Developed a series of flip algorithms with emphasis on execution order flexibility.
• Implemented algorithms for both Central Processing Units (CPUs) and Graphics Processing Units (GPUs).
• Conducted experiments to compare the performance of GPU implementations against single-threaded CPU algorithms.

Main Results:

• Proposed provably correct flip algorithms suitable for parallel execution.
• Achieved up to two orders of magnitude speedup with the GPU implementation for constructing triangulations and convex hulls from point sets.
• Demonstrated the feasibility and efficiency of parallel flip algorithms on modern hardware.

Conclusions:

• The developed flip algorithms enhance flexibility in execution order, facilitating parallelization.
• GPU implementations provide substantial performance improvements for geometric structure construction.
• This work paves the way for more efficient parallel algorithms in computational geometry.