6 VORONOI Re-gridding and Interpolation Service

It is indeed remarkable that such a diverse collection of problems can be solved by a single unifying structure. However, this is not the whole story: from other applications, to be examined later, we shall not cease being surprised at the versatility of the Voronoi diagram.

F.P. PREPARATA AND M.I. SHAMOS [95]

• 6.1 Background
  • 6.1.1 Motivation
  • 6.1.2 Taxonomy of Problems
  • 6.1.3 The Generalized Problem
• 6.2 Architectural Design
  • 6.2.1 Related Problems and Related Work
  • 6.2.2 The Delaunay Triangulation
  • 6.2.3 Problem Decomposition and Architecture
  • 6.2.4 Scope and Possible Extensions
• 6.3 Data Structures
  • 6.3.1 The Dual Doubly Connected Edge Lists (DCELs)
    • Access Macros
  • 6.3.2 The Bucket Quadtree
• 6.4 Boundary Refinement
  • 6.4.1 Motivation
  • 6.4.2 Refinement Criterion
  • 6.4.3 Boundary Grid Point Insertion
  • 6.4.4 Boundary Refinement Algorithm
• 6.5 Triangulation
  • 6.5.1 Quadtree-divide-and-conquer Voronoi Tessellation
  • 6.5.2 The Merge Step
  • 6.5.3 Alternative Methods
• 6.6 Interpolation
  • 6.6.1 Background and Problem Definition
  • 6.6.2 Architecture
  • 6.6.3 Choice of the Interpolating Equation
    • Locality and Monotonicity
• 6.7 Implementation Aspects
  • 6.7.1 Performance
  • 6.7.2 Test and Demonstration Examples
    • Boundary-Boundary Triangulation
    • Geometry-Conforming Grid Point Cloud Triangulation
    • Interpolation