Localizing the delaunay triangulation and its parallel implementation

Renjie Chen, Craig Gotsman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

We show how to localize the Delaunay triangulation of a given planar point set, namely, bound the set of points which are possible Delaunay neighbors of a given point. We then exploit this observation in an algorithm for constructing the Delaunay triangulation (and its dual Voronoi diagram) by computing the Delaunay neighbors (and Voronoi cell) of each point independently. While this does not lead to the fastest serial algorithm possible for Delaunay triangulation, it does lead to an efficient parallelization strategy which achieves almost perfect speedups on multicore machines.

Original languageEnglish (US)
Title of host publicationTransactions on Computational Science XX
Subtitle of host publicationSpecial Issue on Voronoi Diagrams and Their Applications
EditorsMarina Gavrilova, C.J. Kenneth Tan, Bahman Kalantari
Pages39-55
Number of pages17
DOIs
StatePublished - Dec 1 2013
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8110
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Delaunay triangulation
  • Voronoi diagram
  • parallel computation

Fingerprint

Dive into the research topics of 'Localizing the delaunay triangulation and its parallel implementation'. Together they form a unique fingerprint.

Cite this