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 C1 and C2 such that every point of C1 has
equal distance to p and to C2, and every point of C2 has equal
distance to C1 and to q. We show by elementary geometric means that
such C1 and C2 exist and are unique. Moreover, for p=(0,1) and
q=(0,-1), C1 is the graph of a function f:R → R,
C2 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.)