Computer Science Colloquium

Distance Trisector Curves and Zone Diagram with Approximation Using Convex Distance Metrics

Tetsuo Asano

Friday, November 17, 2006, 2006 11:30 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185

Colloquium Information:


Chee, (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

top | contact