**Discrete Mathematics and Optimization Seminar**

**Tetsuo Asano**

* Japan Advanced Institute of Science and Technology*

Monday October 24th at 4.30pm

* Burnside 1205*

**Title. ***Voronoi Diagram with Neutral Zones based on Distance Trisector.*

**Abstract. **
Given points *p* and *q* in the plane, we are interested in separating
them by two curves *C*_{1} and *C*_{2} such that every point of *C*_{1} has

equal distance to *p* and to *C*_{2}, and every point of *C*_{2} has equal
distance to *C*_{1} and to *q*. We show by elementary geometric means that

such *C*_{1} and *C*_{2} exist and are unique. Moreover, for *p=(0,1)* and
*q=(0,-1)*, *C*_{1} is the graph of a function *f:R → R*,
*C*_{2} is the graph of *-f*,

and *f* is convex and analytic (i.e., given by a convergent power series at a
neighborhood of every point). We conjecture that *f* is not expressible

by elementary functions and, in particular, not algebraic. We provide an algorithm that,
given *x ∈R* and μ>0, computes an approximation

to *f(x)* with error at most μ in time
polynomial in *log (1+|x|)/μ*.

The separation of two points by two ``trisector'' curves considered here
is a special (two-point) case of a new kind of Voronoi diagram,

which we call the {\em Voronoi diagram with neutral zone}.

Joint work with Jiri Matousek (Charles Univ.) and Takeshi Tokuyama (Tohoku Univ.)