Computer Science Colloquium
Distance Trisector Curves and Zone Diagram with Approximation
Using Convex Distance Metrics
Friday, November 17, 2006, 2006 11:30 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185
Colloquium Information: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html
Chee Yapyap@cs.nyu.edu, (212) 998-3115
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 \rightarrow 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.
A zone diagram is a new variation of the classical notion of Voronoi
diagram. Given points (sites) $p_1,\ldots,p_n$ in the plane, each $p_i$
is assigned a region $R_i$, but in contrast to the ordinary Voronoi
diagrams, the union of the $R_i$ has a nonempty complement, the neutral
zone. The defining property is that each $R_i$ consists of all $x\in R2$
that lie closer (non-strictly) to $p_i$ than to the union of all the other
$R_j$, $j\ne i$. Thus, the zone diagram is defined implicitly, by a
``fixed-point property,'' and neither its existence nor its uniqueness
seem obvious. We establish existence using a general fixed-point result
(a consequence of Schauder's theorem or Kakutani's theorem); this proof
should generalize easily to related settings, say higher dimensions.
The Zone Diagram has many mathematically interesting properties, but
theoretically it is quite hard even to draw it. Then, we introduce
a notion of convex distance metric by which we can draw Voronoi edges
as polygonal chains.
Refreshments will be served
| contact firstname.lastname@example.org