Fast Voronoi Diagrams and Offsets on Triangulated Surfaces

Abstract

We apply the Fast Marching Method on triangulated domains to efficiently compute Voronoi diagrams and offset curves on triangulated manifolds. The computational complexity of the proposed algorithm is optimal, O(M log M), where M is the number of vertices. The algorithm also applies to weighted domains in which a different cost is assigned to each surface point.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2000
Accession Number
ADP012029

Entities

People

  • James A. Sethian
  • Ron Kimmel

Organizations

  • Technion – Israel Institute of Technology

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Cartesian Coordinates
  • Computational Complexity
  • Computations
  • Computer Graphics
  • Computer Vision
  • Computer-Aided Design
  • Computers
  • Equations
  • Geometry
  • Graphics
  • Grids
  • Image Processing
  • Mathematics
  • Pattern Recognition
  • Technical Information Centers
  • Triangles

Fields of Study

  • Computer science

Readers

  • Computational Fluid Dynamics (CFD)
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Geodesy