DIMACS Theoretical Computer Science Seminar

Title: Distance k-sectors and zone diagrams

Speaker: Akitoshi Kawamura, University of Tokyo

Date: Wednesday, October 31, 2012 11:00-12:00pm

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


The bisector of two nonempty sets P and Q in a metric space (e.g. Euclidean plane) is the set of all points at equal distance from P and from Q. A trisector of P and Q is a pair (C_1, C_2) of sets such that C_i is the bisector of C_{i-1} and C_{i+1} for i = 1, 2, where C_0 = P and C_3 = Q. Likewise we can define what a k-sector between P and Q is.

Zone diagrams between sets P_1, ..., P_n are a generalization of trisectors obtained by going from two sets to n sets, in the analogous way that a Voronoi diagram is the "bisector" between n sites.

In the seminar I will discuss the existence, uniqueness and computational issues related to k-sectors and zone diagrams.

Based on joint works with Keiko Imai, Jií Matoušek, Daniel Reem and Takeshi Tokuyama.

See: http://paul.rutgers.edu/~yixinxu/theory-fall12.html