Campus Event Calendar
Event Entry
What and Who
Voronoi Diagrams with Neutral Zones Based on Distance Trisector Curves
Prof. Tetsuo Asano
Ringvorlesung
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 10 November 2005
13:00
-- Not specified --
45 - FR 6.2 (E1 3)
016
Saarbrücken
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: {\cal R} \rightarrow {\cal 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\in {\cal R}$ and $\epsiron>0$, computes
an approximation to $f(x)$ with error at most $\epsiron$ in time polynomial in
$\log \frac {1+||x||}{\epsiron}$.
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}.
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: {\cal R} \rightarrow {\cal 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\in {\cal R}$ and $\epsiron>0$, computes
an approximation to $f(x)$ with error at most $\epsiron$ in time polynomial in
$\log \frac {1+||x||}{\epsiron}$.
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}.
Contact
--email hidden
passcode not visible
logged in users only
Veronika Weinand, 11/07/2005 14:55
Veronika Weinand, 10/19/2005 13:11
Veronika Weinand, 10/19/2005 13:08 -- Created document.
Veronika Weinand, 10/19/2005 13:11
Veronika Weinand, 10/19/2005 13:08 -- Created document.