Southern California Conferences for Undergraduate Research

Southern California Conferences for Undergraduate Research

Constructing Doubly Connected Edge Lists on the GPU


Ivan Espinosa, Allen Hsu


Kevin Wortman, Assistant Professor Department of Computer Science, California State University Fullerton

Abstract. Our research entails building the doubly connected edge list (DCEL) on the Graphics Processing Unit (GPU) and then analysing the time differences between it and the Central Processing Unit (CPU). The doubly connected edge list (DCEL) is a pivotal aspect of many algorithms involving computational geometry, which finds applications in geographical information systems (GIS), computer aided design (CAD), graphics and data visualization, gaming, and spatial databases. By allowing algorithms access to topological information about a N-Dimensional surface, the DCEL can be used as a basis for many computational geometric algorithms. However, the work required to generate such an arrangement of hyperplanes can be astronomical depending on the number of inputs. In recent years, the number of processors on GPUs have grown immensely. This enables us to process hundreds of inputted data in parallel. We hypothesise that our results will show the algorithm can be successfully implemented on GPU and this implementation will be comparable or superior to a CPU implementation.

Presented by:

Allen Hsu, Ivan Espinosa


Saturday, November 17, 2012


3:00 PM — 3:15 PM


Bell Tower 2505

Presentation Type:

Oral Presentation


Computer Science