Class Presentation on November 8, 2002
By Parag Jain
- Voronoi Diagrams:The partitioning of a plane with n points into n convex polygons such that each polygon contains exactly one point and every point in a given polygon is closer to its central point than to any other.
- Delaunay Triangulations:The Delaunay triangulation is a triangulation which is equivalent to the nerve of the cells in a Voronoi diagram, i.e., that triangulation of the convex hull of the points in the diagram in which every circumcircle of a triangle is an empty circle.
- The Delaunay triangulation and Voronoi diagram in are dual to each other.
- Certain algorithms, like the one DMS (that I used in this project) uses, use the concept of finding the nearest neighbor to compute SES.
Next slide