### 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

Abstract:

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