CS 269S, Fall 2017: Theory Seminar
Bren Hall, Room 1300, 1pm
October 20, 2017:

The combinatorial complexity of stable-matching Voronoi diagrams

Nil Mamano

In this talk, we discuss the proper way to generalize Voronoi diagram to regions of any prespecified size. After we propose our candidate generalization, the stable-matching Voronoi diagrams, we discuss its combinatorial complexity, that is, we give upper and lower bounds for the number of faces, edges, and vertices of the diagram.

Based on unpublished work by Gill Barequet, David Eppstein, Michael Goodrich, and Nil Mamano