English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Geometric algorithms rely on predicates, among them, the 2D and 3D orientation and incircle tests are important ones. Shewchuk’s adaptive floating-point predicate is a well-known C implementation, which is embedded in many computational geometry algorithm libraries. Recently, GPU with its enormous parallel computing power has been used widely in many disciplines for general purpose computation, including computational geometry. In this paper, we propose GPredicates, a CUDA implementation of the geometric predicates, which can be used as the GPU version of Shewchuk’s work. In the GPredicates, the original predicate program is split into two GPU kernels: a fast check and an exact check kernel. In most cases, the fast check is enough, only a few threads go into the exact check which requires a lot more temporary memory. Furthermore, we use on-the-fly compaction on the shared memory to collect all threads that need to go into the exact check kernel to speed up the compaction time. According to our experiments in constructing 2D and 3D Delaunay triangulation and 2D constrained Delaunay triangulation for both synthetic and real-world datasets, such a GPU technique can speed up the computing time for predicates by 3 to 4 times and can be used as the GPU version of Shewchuk’s work for other computational geometry problems.

GPredicates: GPU Implementation of Robust and Adaptive Floating-Point Predicates for Computational Geometry