You can contact me at aloupis.greg -at- gmail
Topics covered on Monday Nov.28 and Thursday Dec.1 are below.
Course notes for both days are in one
PDF file.
On Nov.28 we covered:
- Basic properties of Voronoi diagram shape. Read chapter 7.1 from textbook.
- halfplane intersection, convexity, vertex degree, boundedness, graph size, cell size, planarity...
- Applications
- Classification, facility location, collision avoidance
- Largest empty circle problem
- The Voronoi game (competitive facility location)
- Computing the Voronoi diagram
- Brute force
- Incremental (quadratic)
- Lower bound
- Intro to Delaunay Triangulation
- Some basic properties (e.g. empty circumcircles)
- Duality w/ Voronoi
- Homework assignment: compute Voronoi diagram with brute force. If possible, allow user to input a fixed number of points.
You may use code from Estimator.java and setup.java, found
here . See today's notes as well.
Links
Other sources (not required to read):
On Dec.1 we covered:
- Incremental computation of Delaunay triangulation (edge flipping)
- Proof of the Delaunay MaxMin angle property (using Thales thm)
- Homework: demonstrate Delaunay incremental
- 3D Paraboloid lifting algorithm for constructing Delaunay triangulation
- Intro to Fortune's sweep algorithm for Voronoi diagram
- Definition and basic properties of medial axis (and Voronoi diagram of segments)
- Definition and basic properties of furthest point Voronoi diagram
- with application to smallest enclosing circle problem
- Intro to Voronoi diagram in L1
- Definitions of some standard proximity graph, and their relations.
- NNG, MST, RNG, GG, DT
- Outline of how some of these can be computed faster than brute force
Reading material:
