GPU Parallel Visibility Algorithm for a Set of Segments Using Merge Path | Zendy

Kevin Zúñiga Gárate | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

GPU Parallel Visibility Algorithm for a Set of Segments Using Merge Path

Author(s) -

Kevin Zúñiga Gárate

Publication year - 2019

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2019.04.005

Subject(s) - computer science , merge (version control) , cuda , speedup , parallel computing , merge algorithm , visibility polygon , workload , parallel algorithm , visibility , path (computing) , algorithm , mathematics , sorting algorithm , operating system , optics , physics , geometry , regular polygon , sorting , polygon covering

In this paper, we present an efficient parallel algorithm for computing the visibility region for a point in a plane among a non-intersecting set of segments. The algorithm is based on the cascading divide-and-conquer technique and uses merge path to evenly distribute the workload between processors. We implemented the algorithm on NVIDIA's CUDA platform where it performed with a speedup up to 76x with respect to the serial CPU version.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research