Delaunay and Voronoi tessellations and minimal simple cycles in triangular region and regular-3 undirected planar graphs

G. M. Seed

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Linear time algorithms are presented which generate the Voronoi tessellation from a Delaunay tessellation and vice versa when the tessellations of convex polygons and triangles are stored as edge-adjacent undirected graphs. These two geometric algorithms lead naturally to two further linear and quadratic graph algorithms for determining the minimal simple cycles or regions in both triangular and regular-3 undirected planar graphs. © 2001 Elsevier Science Ltd.

Original languageEnglish
Pages (from-to)339-351
Number of pages13
JournalAdvances in Engineering Software
Volume32
Issue number5
DOIs
Publication statusPublished - May 2001

Keywords

  • Computational Geometry
  • Delaunay and Voronoi tessellations
  • Graph algorithms

Fingerprint Dive into the research topics of 'Delaunay and Voronoi tessellations and minimal simple cycles in triangular region and regular-3 undirected planar graphs'. Together they form a unique fingerprint.

  • Cite this