Discrete Geometry: Voronoi Diagrams and Fortune's Method

Event Date: 

Wednesday, November 20, 2013 - 2:00pm to 3:00pm

Event Location: 

  • 4607B South Hall

Event Contact: 

Michael Dougherty

Email: dougherty@math.ucsb.edu

Speaker: Josh Pankau

Title: Voronoi Diagrams and Fortune's Method

Abstract: Given a finite collection S of points in the plane, each point in S generates a region in the plane that contains all points closest to it in relation to all other points of S. This subdivides the plane into convex polygonal regions, and such a subdivision is called a Voronoi Diagram. Voronoi Diagrams have many applications ranging from Astronomy to Zoology (see what I did there?), but are very tedious to calculate straight from the definition.

In this talk I will discuss Fortune's Method, which is a more efficient way of building the Diagram, some properties of Voronoi Diagrams, and their relationship with Delaunay Triangulation.