DIMACS Theoretical Computer Science Seminar

Title: Mollified Zone Diagrams and Their Computation

Speaker: Sergio C. de Biasi, Rutgers University

Date: Wednesday, October 6, 2010 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


The notion of the "zone diagram" of a finite set of points in the Euclidean plane is an interesting and rich variation of the classical Voronoi diagram, introduced by Asano, Matousek, and Tokuyama (2007). Here, we define the more inclusive notion of a "maximal territory diagram". The proof of existence of maximal territory diagrams depends on less restrictive initial conditions and is thus conveniently established via Zorn's lemma in contrast to the use of fixed-point theory in proving the existence of a zone diagram. A zone diagram is a particular maximal territory diagram satisfying a sharp dominance property. We give a characterization for maximal territory diagrams which allows recognition of maximality of certain subsets called "territory diagrams," as well as that of their iterative improvement toward maximality. Maximal territory diagrams offer their own interesting theoretical and computational challenges.

Joint work with Bahman Kalantari (Rutgers University) and Iraj Kalantari (Western Illinois University)

Previous work on this topic was presented at ISVD 2010 in Quebec, Canada http://www.computer.org/portal/web/csdl/doi/10.1109/ISVD.2010.10