Document Type

Article

Language

eng

Publication Date

1-2019

Publisher

Springer

Source Publication

Lecture Notes in Computer Science

Source ISSN

0302-9743

Abstract

Line segment intersection is one of the elementary operations in computational geometry. Complex problems in Geographic Information Systems (GIS) like finding map overlays or spatial joins using polygonal data require solving segment intersections. Plane sweep paradigm is used for finding geometric intersection in an efficient manner. However, it is difficult to parallelize due to its in-order processing of spatial events. We present a new fine-grained parallel algorithm for geometric intersection and its CPU and GPU implementation using OpenMP and OpenACC. To the best of our knowledge, this is the first work demonstrating an effective parallelization of plane sweep on GPUs.

We chose compiler directive based approach for implementation because of its simplicity to parallelize sequential code. Using Nvidia Tesla P100 GPU, our implementation achieves around 40X speedup for line segment intersection problem on 40K and 80K data sets compared to sequential CGAL library.

Comments

Accepted version. Lecture Notes in Computer Science, Vol. 11381 (January 2019): 114-135. DOI. © 2019 Springer. Used with permission.

Download
Puri_13306acc.docx (409 kB)
ADA Accessible Version

Share

COinS