数理解析研究所講究録
第 833 巻 1993 年 110-119

110

Generalized Geometric Fitting Problems andWeighted Dynamic Voronoi Diagrams
中央大学理工学部情報工学科 今井桂子 (Keiko Imai)
東京大学理学部情報科学科 今井浩 (Hiroshi Imai)

1. Introduction
points is fundamental problem in image proGeometric fitting two similar sets ofcessing and pattern recognition. This minimax geometric fitting problem between two
similar sets of points is considered in [10]. For example, it arises in an industrial robot
attaching a pin-grid-array type LSI to a board by using visual sensors. The robot firsttakes an image of the pins of LSI by its visual sensor. Then it tries to fit the LSI package
to the corresponding patterns on the board by geometric operations such as translation
and rotation. The patterns are a collection of disks or squares of the same size. Using thefurthest Voronoi diagram for moving points in the plane, this geometric fitting problem
has been solved in $O(n^{2}\lambda_{7}(n)\log n)$ time [10].
In a more general setting, the following variants of the fitting problem should be considered. (a) In the case that there are some points which cannot be put into the corresponding
disks, minimize the number of such points. (b) In the case that the radii of disk patterns
are different from one another, solve this non-uniform geometric fitting problem (Figure1). Recently, the Voronoi diagrams for moving objects have been investigated in connection with motion planning in robotics and geometric optimization problems[2,5,8,9,10]. In
this paper, to solve the generalized problem (b), we extend the concept of the weighted
points in the plane to the one for the case that the coordinates
Voronoi diagram forand the weights of each point are represented by polynomials or rational functions of aparameter. We show that the combinatorial complexity of this dynamic Voronoi diagram
where
is
is some fixed number determined by the degree of the functions
andis the maximum length of $(n, s)$ Davenport-Schinzel sequence. Since a lower
bound of this dynamic Voronoi diagram can be shown to be, our bounds are tightwithin $\log^{*}n$ factor, which beats bounds withinfactor.
2. Generalized Geometric Fitting Problems
We here formulate the geonetric fitting problems for two corresponding sets of points.
The non-weighted problem has been formulated as follows [10]. Given two sets $S=\{s_{j}=$$(x_{j}, y_{j})|j=1,$} and $T=\{t_{j}=(u_{j}, v_{j})|j=1, \cdots, n\}$ -of points in the plane, translate, rotate (or transform in a more complicatedsuch thatis associated withway) $and/or$ scale the set
simultaneously so that the maximum of the(or)
distances, according to each pattern, between
and the transformed
is minimized.
$n$

$n$

$O(n^{2}\lambda_{s}(n))$$s$$\lambda_{s}(n)$$\Omega(n^{3})$$n^{\epsilon}$$\cdots,$ $n$$t_{j}$$s_{j}$$S$$L_{2}$$t_{j}$$s_{j}$$L_{\infty}$

111$\circ$

$O$

$O$

$O$

$\circ$$\circ$$\circ$

$O$

$O$

$0$

$\circ$$\circ$$O$$O$$\circ$$O$$\circ$Figure 1. Geometric fitting of distorted grid points with disks with different radii
For example, in the case that the patterns are disks, and translation and rotation are usedas geometric operations, the problem is expressed as follows:$\min_{z,0\leq\theta<2\pi}j=1,\cdots nmax,\Vert s_{j}e^{i\theta}-t_{j}-z\Vert$,

andare identified with complex numbers. respectively.
where
and
and
is an angle $(0\leq\theta<2\pi)$ and theis translated by making the origin to $z=$$x+iy$ .
denotes the Euclidean norm. Using the furthest Voronoi diagram for moving
points in the plane, this geometric fitting problem can be solved in $O(n^{2}\lambda_{7}(n)\log n)$ time$u_{j}+iv_{i}$$x_{i}+iy_{i}$$t_{j}$$s_{j}$$S$$\theta$$\Vert\cdot\Vert$

norm. Defining a points
lewritten asin$L_{2}$$p_{j}(\theta)$by$S_{)}e^{1}\theta-t_{J}$in the complex plane, the problem is$0 \leq^{l}<n_{\theta}in_{2\pi}(\min_{z}j)\max_{=1,\cdot\cdot 71}\Vert p_{J}(\theta)-z\Vert)$.
Fixing , the problem becomes the minimum enclosing circle problem forpointsThe minimum enclosing circle problem can be solved by using the furthest Voronoi diagram.
We consider the generalized case where the radii of disk patterns are different frolll
one another and solve this non-uniform geometric fitting problem (Figure 1). The weighted
Voronoi diagram for moving points can be used to solve this generalized problem.
There are various kinds of Voronoi diagram and efficient algorithms to construct sucha diagram. The weighted Voronoi diagram is one of these generalizations of the Voronoi
diagram.
$(i=1, \cdots, n)$ in the EuclideanLetdenote a set ofweighted points
plane. Each point
is associated with a non-negative real weight $w;$ . The weighted
distance
betweenand an arbitrary pointinis defined by $d_{i}(p)=$$\iota()\iota\sqrt{(x-x_{l})^{2}+(y-y_{i})^{2}}$ , where the coordinates of, $(x, y)$ . $res$ pecare
tively. The weighted Voronoi region ofis given by$\theta$

$n$

$S$

$n$

$p_{i}$$p_{\dot{l}}$$d_{i}(p)$$E^{2}$$p$$p_{i}$$p_{i},$$p$$p_{t}$$V(p_{i})= \bigcap_{i\neq\dot{)}}\{p|d_{i}(p)<d_{J}(p)\})$$(x_{i}, y_{i})$$p_{j}(\theta)$

112

Figure 2. Weighted Voronoi diagram

and the subdivision of the Euclidean plane defined by the weighted Voronoi regions is(Figure 2). The weighted Voronoi diagram forcalled the weighted Voronoi diagram ofpoints in the plane can be constructed in $O(n^{2})$ time [4]. The algorithm in [4] is
fixed
faces, edges and vertices.
optimal as the diagram can consist of
The weighted Voronoi diagram for moving points can be used to solve the problem(b), since the radii of the disks may be considered as weights of their centers. Suppose thatand radius
point
should be put into disk with centerin the pattern. By rotating
and further translating it by $z,$
is the corresponding disk
the setof points by. Then, all the points incan be put into the corresponding
iff 1
disks iff the following value
$S$

$n$

$\Theta(n^{2})$$t_{j}$$s_{j}$$S$$r_{j}$$\theta$$s_{j}$$S$$s_{j}e^{i\theta}-t_{j}-z\Vert\leq r_{j}$$\min_{z,0\leq\theta<2\pi}j1,\cdots n\max_{=},\frac{1}{r_{j}}\Vert s_{j}e^{i\theta}-t_{j}-z\Vert$is less than or equal to 1.
can be considered as the weight of.
Hence, the weighted Voronoi diagram for moving points can be applied to its generalized
geometric fitting problems.
To solve the geometric fitting problems, we need the weighted furthest Voronoi diagram. Although the furthest Voronoi diagram is different from the nearest one, the below
arguments hold with a slight modification. Hence, we consider the dynamic nearest Voronoi
diagram in the below arguments.
$p_{j}(\theta)=s_{j}e^{i\theta}-t_{j}$$\frac{1}{r_{j}}$3. Definitions and Some Properties of the Weighted Dynamic Voronoi Diagram
In the weighted Voronoi Diagram, if the regions of two point
andintersecteach other, then the intersection is a subset of the curve defined by the equation $d_{i}(p)=$. The equidistant curve fromandis a circle, and one of the points
whose weight is greater than that of the other is enclosed in the circle, which is called the$p_{i}$$d_{j}(p)$$p_{i}$$p_{j}$$p_{j}$$p_{i},$$p_{j}$

113
Apollonius’ circle forradius:and$p_{i}$$p_{ij}=( \frac{w_{i}^{2}x_{i}-w_{j}^{2}x_{j}}{w_{i}^{2}-w_{j}^{2}},$$p_{j}$. Let$p_{ij}$$\frac{w_{i}^{2}y_{i}-w_{j}^{2}y_{j}}{w_{i}^{2}-w_{j}^{2}})$,be the center of the circle$C_{ij}$and$r_{ij}$be its$r_{ij}= \frac{w_{i}w_{j}}{|w_{i}^{2}-w_{j}^{2}|}\sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}}$.

Note here that the equidistant curve from the two points with same weights is a line.
In the weighted Voronoi diagram, the set of the equidistants from three points ofconsists of at most two points. See Figure 2.
For each ,

$S$

$i$

$z=f_{i}(x, y)=w_{i}\sqrt{(x-x_{i})^{2}+(y-y_{i})^{2}}$. When the cone $z=f_{i}(x, y)$ intersects
is a cone with the singular point at.
another cone $z=f_{j}(x, y)$ , the intersection of two cones is a quadratic curve in
The projection of the quadratic curve is nothing but the Apollonius’ circle for.
functions $f_{i}(x, y)$ . Projecting down thisConsider the lower envelope of the graphs oflower envelope to the $(x, y)$ -plane yields the weighted Voronoi diagram for.
points
The weighted Voronoi diagram may be extended to that for moving points in the
points $p_{i}(t)=(x_{i}(t), y_{i}(t))$ with weights
parametrized
following way. Consider
andare functions of , which are polynomials
by in the plane, where $x_{i}(t),$or rational functions of . The degrees of these functions are assumed to be independent. To simplify our discussion, it is also assumed that these functions are differentoffrom one another. As we mentioned before, for fixed , the weighted Voronoi diagram
foris the orthogonal projection of the lower envelope of functions $z=f_{i}(x, y)=$$w_{i}\sqrt{(x-x_{i})^{2}+(y-y_{i})^{2}}$ of two variables
and . In a similar way, the problem of
constructing the weighted dynamic diagram may be regarded as computing the lower
envelope offunctions$(x_{i}, y_{i}, 0)$$E^{3}$$p_{i},$$p_{j}$$n$$n$$p_{i}$$w_{i}(t)$$n$$y_{i}(t)$$t$$w_{i}(t)$

$t$

$t$

$n$

$t$

$p_{i}(t)$

$x$

$y$

$n$

$f_{i}(x, y, t)=w_{i}(t)\sqrt{(x-x_{i}(t))^{2}+(y-y_{i}(t))^{2}}$of three variables $x,$

$y$

and

$t$

. Define $f(x, y, t)$ by$f(x, y, t)= \min_{i=1,\cdots,n}f_{i}(x, y, t)$.

Now the problem is how to compute $f(x, y, t)$ .
For this function $f(x, y, t)$ , the minimum $di$agram is a subdivision of $(x, y, t)$ -spaceattaining the minimum in the definition ofsuch that, with each region, a function
for any point in the region is associated. This is nothing but the projection of the pointwise
minimum of these functions onto the $(x, y, t)$ -space. The intersection of this diagram withthe plane $t=t_{0}$ is a weighted Voronoi diagram for $t=t_{0}$ , and the whole diagram iscalled the weighted dynamic Voronoi diagram.
, each region of the minimum diagram of
By the assumptions on
consists ofa maximal connected 3-dimensional set of points at which the minimum is attained by a$f$$f_{i}$$p_{i}(t)$

$f$

114
. The faces, edges and vertices of the subdivision consist of points at which thefunction
minimum is attained simultaneously by two, three and four, respectively, functions. It iseasy to see the following properties of the intersections of the trivariate functions $f_{i}(x, y, t)$
by solving the simultaneous equations each of which defines a function $f_{i}(x, y, t)$ in thewill be often. In the sequel, variables $x,$ $y,$ of
4-dimensional Euclidean space$f_{i}$$E^{4}$$t$$f_{i}$

omitted.

.
Lemma 1: (1) For each $i\neq j,$ $f_{i}(t, x, y)=f_{j}(t, x, y)$ is a connected surface inof distinct indices, $f_{i}(t)=f_{j}(t)=f_{k}(t)$ consists of at most(2) For each triple $i,$ $j,$
two points for fixed
and $f_{i}=f_{j}=f_{k}$ is a curve with parameter . The curve has at
most two components and is discontinuous at most constant times.
(3) For four distinct indices $i,$ $j,$
and $l,$ $f_{i}=f_{j}=f_{k}=fi$ consists of at mostpoints, whereis a constant.
$E^{4}$

$k$

$t$

$t$

$k$

$s$

$\square$$s$

4. Combinatorial Complexity of the Minimum Diagram and Constructing the
DiagramA trivial bound on the number of vertices on the minimum diagram is $O(n^{4})$ , sinceby Lemma 1. However, this is loose as shown
the number of vertices is bounded by
below.
Letandbe distinct two indices, and fix them. Let
be the oriented line
andand the orientation is defined as follows. When weight ofpassingisless than that ofto. There are twois oriented fromon the oriented
line which are at equal distances fromand. One of the two points is between. The other is denoted byandand the point is denoted by. See
Figure 3(a). Draw the circle
for each $k\neq i,j$ and consider the intersection points of. Those intersection points are nothing but the equidistants from.
, we define four points
Using the intersection points ofandas follows. $d_{E}(p, q)$ is the Euclidean distance betweenand .
$s(_{4}^{n})$

$i$

$j$

$p_{i}(t)$$l_{ij}$$p_{j}(t)$$p_{j},$$p_{i}$$p^{\downarrow}oints$$l_{ij}$$p_{i}$$p_{j}$$p_{i}(t)$$p_{i}(t)$$p_{j}(t)$$p_{j}(t)$$\overline{m}_{ij}$$m_{ij}$$C_{jk}$$C_{ij},$$C_{jk}$$p_{i},$$C_{ij},$$q_{k}^{+}(t),$$C_{jk}$$\tilde{q}_{k}^{-}(t)$$p$Case 1: $d_{E}(p_{ij},p_{jk})<r_{ij}+r_{jk}$ and $d_{E}(p_{ij},p_{jk})>|r_{ij}-r_{jk}|$ .
In this case,at two points. Letintersects
and
and
.
connecting$C_{jk}$$C_{ij}$$q$

Case 1-1:

$q’$

$q$

$s_{k}$$p_{j},$$p_{k}$$q_{k}^{-}(t),\tilde{q}_{k}^{+}(t)$$q$be the line segment$q’$$s_{k}\cap l_{ij}=\emptyset$.

Case 1-1-1: Consider the case whereintersects
and these two intersection points
are between
and. When the segment is on the right side of, choosethe point which is counterclockwisely nearer along the circle frombetweenand letbe the point andandbe the other. See Figure 3(a). When the$C_{jk}$$m_{ij}$$l_{ij}$$\overline{m}_{ij}$$l_{ij}$$m_{ij}$$q’$$q_{k}^{-}$$q_{k}^{+}$

$q$

115

(c) Case 1-2-1(b) Case 1-1-2(a) Case 1-1-1

Figure 3. Definitions ofsegment is on the left side ofand letthe circle fromdefine$m_{ij}$$l_{ij}$$q_{k}^{+}$$q_{k}^{+},$$q_{k}^{-},\tilde{q}_{k}^{+}$and(d) Case 1-2-2$\tilde{q}_{k}^{-}$, choose the point which is clockwisely nearer alongbe the other. Moreover, webe the point and$q_{k}^{-}$$\tilde{q}_{k}^{+}=q_{k}^{+},\tilde{q}_{k}^{-}=q_{k}^{-}$, oratintersects
does not intersect
Case 1-1-2: Consider the case whereare between those two points. When the segment is on
two points and, choose the point which is counterclockwisely nearer along thethe right side ofbe the point andcircle frombetweenandand letbe the other.
$q_{k}^{-}=-\infty$ .
Furthermore, we define
If, then we consider), where(resp.
are the point
and we assume
is on the right (resp. left) side of. See Figure 3(b). When the segment is on, choose the point which is clockwisely nearer along the circle
the left side of
betweenbe the point andfromandbe the other.
and letFurthermore, we define. If, then we consider$C_{jk}$$l_{ij}$$C_{jk}$$l_{ij}$$m_{ij},\tilde{m}_{ij}$$l_{ij}$$m_{ij}$

$q’$

$q$

$q_{k}^{+}$$\tilde{q}_{k}^{+}=+\infty$$\tilde{q}_{k}^{-}=\overline{m}_{ij}$)$\pm\tilde{m}_{ij}$$\tilde{q}_{k}^{-}=+\overline{m}_{ij}$$\tilde{q}_{k}^{-}$$-\overline{m}_{ij}$$+\overline{m}_{ij}$$\tilde{m}_{ij}$$l_{ij}$$l_{ij}$$q$$m_{ij}$$q’$$\tilde{q}_{k}^{+}$$q_{k}^{-}$$q_{k}^{+}=+\infty,\tilde{q}_{k}^{-}=-\infty$$\tilde{q}_{k}^{+}=-\tilde{m}_{ij}$Case 1-2:$\tilde{q}_{k}^{+}=\tilde{m}_{ij}$.
.

$s_{k}\cap l_{ij}\neq\emptyset$

at two points.
intersects
is between these intersection
Case 1-2-1: Consider the case where $w_{j}>w_{k}$ and, or $w_{j}<w_{k}$ andandis between these intersection points
points of. Define the point lying on the right side of
among
of
and
and
, is called. The other point, lying on the left side of. We define
to be
and
. See Figure 3(c).
as$C_{ik}$$l_{ij}$$m_{ij}$$C_{jk}$$l_{ij}$$\tilde{m}_{ij}$$C_{jk}$$l_{ij}$$l_{ij}$$q_{k}^{+}$$\tilde{q}_{k}^{+}$$l_{ij}$$\tilde{q}_{k}^{-}$

$q$

$q’$

$q_{k}^{-}$$\tilde{q}_{k}^{+}=q_{k}^{+},\tilde{q}_{k}^{-}=q_{k}^{-}$

is between these intersection
Case 1-2-2: Consider the case where $w_{j}>w_{k}$ and, or $w_{j}<w_{k}$ andis between these intersection points
andpoints of$\tilde{m}_{ij}$$l_{ij}$$C_{jk}$$m_{ij}$

116
among
and
to
. Define the point lying on the right side ofand,, is called. Set. The other point, lying on the left side of$q_{k}^{-}=-\infty$ .
(resp.
), then we consider
See Figure 3(d). If).
(resp.

ofbe$C_{jk}$$l_{ij}$$l_{ij}$$\tilde{q}_{k}^{+}=+\infty$$q_{k}^{+}$$l_{ij}$$\tilde{q}_{k}^{-}$

$q’$

$q$

$q_{k}^{+}=\overline{m}_{ij}$$\tilde{q}_{k}^{-}=\overline{m}_{ij}$$q_{k}^{+}=-\overline{m}_{ij}$$\tilde{q}_{k}^{-}=+\overline{m}_{ij}$Case 2: $d_{E}(p_{ij},p_{jk})=r_{ij}+r_{jk}$ .
In this case, there is only one intersection point ofand define four points byintersection point$C_{ij}$

and$C_{jk}$$q_{k}^{+}=q_{k}^{-}=\tilde{q}_{k}^{+}=\tilde{q}_{k}^{-}=q$$q$. We call the.

Case 3: $d_{E}(p_{ij},p_{jk})>r_{ij}+r_{jk}$ or $d_{E}(p_{ij},p_{jk})<|r_{ij}-r_{jk}|$ .
.
andThere is no intersection point ofCase 3-1: In the cases that $d_{E}(p_{ij}-p_{jk})>r_{ij}+r_{jk}$ or $d_{E}(p_{ij}-p_{jk})<-r_{ij}+r_{jk}$ , the.
four points are defined by.
Case 3-2: $1fd_{E}(p_{ij}-p_{jk})<r_{ij}-r_{jk}$ , we set$C_{ik}$$C_{ij}$$q_{k}^{+}=\tilde{q}_{k}^{+}=+\infty,$$q_{k}^{-}=\tilde{q}_{k}^{-}=-\infty$$q_{k}^{+}=\tilde{q}_{k}^{+}=-\infty,$$q_{k}^{-}=\tilde{q}_{k}^{-}=+\infty$be the Euclid distance between
andLet
is infinity and the point
We consider the distance between a point and$-\infty)$ is on the right (resp.
left) side of. We define four functions
by using four points
andas follows.
and$d_{k}^{-}(d_{k}^{+},\tilde{d}_{k}^{-},\tilde{d}_{k}^{+})$$q_{k}^{-}(q_{k}^{+},\tilde{q}_{k}^{-},\tilde{q}_{k}^{+})$$p_{ij}$$\pm\infty$$l_{ij}(t)$$q_{k}^{+},$$\tilde{g}_{k}^{-}$$g_{k}^{+}(t)=\{_{-d}+d_{k}^{+}\lambda$$q_{k}^{-},\tilde{q}_{k}^{+}$$+\infty$$g_{k}^{+},$.

(resp.

$g_{k}^{-},\tilde{g}_{k}^{+}$$\tilde{q}_{k}^{-}$$(q_{k}^{+}(qLisonthe1eftsideofl_{ij}(t))isontherightsideofl_{ij}(t))$$g_{k}^{-}(t)=\{+d-d_{\frac{k-}{k}}(q_{\frac{k-}{k}}(qisontherightsideofl_{ij}(t))isontheleftsideofl_{ij}(t))$

For
and

$\tilde{g}’(t)$$\tilde{g}_{k}^{+}(t)=\{+\tilde{d}_{k}^{+}-\tilde{d}_{k}^{+}$$(\tilde{q}_{+}^{+}(\tilde{q}_{k}^{k}isontherightsideofl_{ij}(t))isonthe1eftsideofl_{ij}(t))$$\tilde{g}_{k}^{-}(t)=\{+\tilde{d}-\tilde{d}_{\frac{k-}{k}}$$(\tilde{q}^{\frac{k-}{k}}(\tilde{q}isonthe1eftsideofl_{ij}(t))isontherightsideofl_{ij}(t))$$g_{k}^{+}(t),$$g_{k}^{-}(t),\tilde{g}_{k}^{+}(t),\tilde{g}_{k}^{-}(t)$, further define $g^{+}(t),$ $g^{-}(t),$ $g’(t),\tilde{g}^{+}(t),\tilde{g}^{-}(t)$as follows:$g^{+}(t)= \min_{k\neq i,j}g_{k}^{+}(t)$,$\tilde{g}^{+}(t)=\min_{k\neq i,j}\tilde{g}_{k}^{+}(t)$,$g^{-}(t)= \min_{k\neq i,j}g_{k}^{-}(t)$,$\tilde{g}^{-}(t)=\min_{k\neq i,j}\tilde{g}_{k}^{-}(t)$,$g’(t)= \max\{g^{-}(t)+g^{+}(t), 0\}$ ,$\tilde{g}’(t)=\max\{\tilde{g}^{-}(t)+\tilde{g}^{+}(t), 0\}$.

$h(t)= \max\{g^{+}(t)-\tilde{g}^{-}(t), 0\}$

Geometric implications of these definitions are given by the following lemma. Note that, which is on the boundary of Voronoi regions, may be disconVoronoi edge
nected and may consist of some connected components.
$V_{i},$$E_{ij}$$V_{j}$$\{e_{ij}\}$Lemma 2: (1) For , suppose $g’(t)>0,$(resp.
). Then,by a function$t$$g_{k}^{+}(t)$$g_{l^{-}}(t)$$g^{+}(t)\neq\pm\infty$$q_{k}^{+}(t)$and) is attained
are Voronoi points which are(resp.

$q_{l^{-}}(t)$$g^{-}(t)\neq\pm\infty$

117, and equidistant from,on the boundaries of Voronoi regions) is the right (resp. left) end point of the leftest component(resp.
.
and the point.
regarding the orientation defined the oriented lineof
) is attained by a(2) For , suppose $\tilde{g}’(t)>0,\tilde{g}^{+}(t)\neq\pm\infty$ (resp.
and). Then,are Voronoi points which are on(resp.
function, and equidistant fromthe boundaries of Voronoi regions$Pj,$) is the right (resp. left) end point of the rightest component(resp.
.
口and the pointofregarding the orientation defined the oriented line
$V_{i},$$q_{k}^{+}(t)$$(p_{l})$$p_{k}$$V_{j},$$(V_{l})$$V_{k}$$p_{i},$$q_{l^{-}}(t)$$E_{ij}$$e_{ij}$$l_{ij}$$m_{ij}$$\tilde{g}^{-}(t)\neq\pm\infty$$t$$\tilde{g}_{k}^{+}(t)$$q_{k}^{+}(t)$$\tilde{g}_{l^{-}}(t)$$V_{i},$$q_{k}^{+}(t)$$(p_{l})$$p_{j}$$V_{j},$$q_{l^{-}}(t)$$(V_{l})$$V_{k}$$p_{i},$$p_{k}$$q_{l^{-}}(t)$$e_{ij}$$E_{ij}$$l_{ij}$$m_{ij}$are composed of maximal connected portions of graphsand. As usual, define the combinatorial complexity of theseandoffunctions to be the maximum number of such maximal connected portions. Also, call.
,an intersecting value of a function $(g^{+}, g^{-}, g’)$ if the functions$0)$ attaining its minimum atandare different for sufficiently small.
The number of intersecting values is nearly equal to the combinatorial complexity. Thisis the maximum length of $(n, s)$complexity can be evaluated as follows, where,
Davenport-Schinzel sequence (e.g., see [1,3,6,11,12]), and is almost linear in . For
and , similar.
Graphs of$g_{k}^{+},$$g^{+},$$g’$$g^{-}$$g_{k}^{+}+g_{l^{-}}$$g_{k}^{-},$

$0$

$t’$

$(g_{k}^{+},$$g_{k}^{-},$$g_{k}^{+}+g_{l^{-}}$$t’+t_{\epsilon}$$t’-t_{\epsilon}$$t_{\epsilon}$$\lambda_{s}(n)$$n$$\tilde{q}^{+}$$h$$\tilde{q}^{-},\tilde{q}’$

(
and
and
) are
Lemma 3: The combinatorial complexity of$O(\lambda_{s+2}(n))$ . These functions can be computed in $O(\lambda_{s+1}(n)\log n)$ time and $O(n)$ space.
may be discontinuous at most a constant number of times from Lemma
Proof: Eachintersect at mostpoints from Lemma 1(3). Hence,
1(2). Any two functions among, similar. Any two funcis $O(\lambda_{s+2}(n))$ [3]. For
the combinatorial complexity ofintersect at most constant times. Then, theandtions amongby a constant factor. The
is within that ofandcombinatorial complexity of, the graph of, similar. For
andtime complexity follows from [7]. Forand .
are composed of maximal connected portions of graphs of
Any two functions among these functions also intersect at most constant times. Hence,by a constant factor.
andis within that of
the combinatorial complexity of$g^{+},$$g’$$g^{-}$$\tilde{g}^{+},\tilde{g}^{-}$$\tilde{g}’$$g_{k}^{+}$$g_{k}^{+}$$s$$g^{+}$$g_{k}^{+},$$g_{k}^{-},$$g_{k}^{+}+g_{l^{-}}$$g^{-}$$0$$g’$$g^{+}$$g^{-}$$\tilde{g}^{+},\tilde{g}^{-}$$h$$\tilde{g}’$$g_{k}^{+},\tilde{g}_{l^{-}},$$h$$g^{+}$$h$$g_{k}^{+}-\tilde{g}_{l^{-}}$$0$$\tilde{g}^{-}$口and , the end points of the leftest and rightest components of Voronoi
Fixingand the middle point
regarding the orientation defined by the oriented lineedge
. However,, are the points $q,$
associated with the function
may be incident to the components ofsome of the Voronoi points on
which
are not the leftest or rightest ones. Such Voronoi points cannot be listed by using thefor the indices $i,$ . The remaining problem is how toandfunctions$i$$j$$E_{ij}$$l_{ij}$$g^{+},$$q’$$m_{ij}$$E_{ij}$$g^{+},$$g^{-},\tilde{g}^{+}$$\tilde{g}^{-}$$g^{-},\tilde{g}^{+},\tilde{g}^{-}$$E_{ij}$

$j$

118
is
maintain such Voronoi points and count the topological changes. We assume that
the Voronoi point which is the end points of neither of the leftest and rightest components
andinstead ofandand $w_{i}<w_{j}<w_{k}$ . In this case, we choose the indicesandfor new indices. It is easily, and define the functions
to see that the point is the end points of the leftest and rightest components of Voronoi
and the middle point
regarding the orientation defined by the oriented lineedge
. Therefore, any end point of Voronoi edge is the end point of the leftest and rightest
and the middle point
component regarding the orientation defined by the oriented line
for a pair of indices ‘, $j’$ .
$q$

$k$

$j$

$g^{+},$$j$$g^{-},\tilde{g}^{+},\tilde{g}^{-}$

$k$

$j$

$E_{jk}$$i$$l_{jk}$$m_{jk}$$l_{i’j’}$$i$$m_{i’j’}$

Theorem 1: The weighted dynamic Voronoi diagram has the combinatorial complexity
of $O(n^{2}\lambda_{s+2}(n))$ , and can be computed in $O(n^{2}\lambda_{s+1}(n)\log n)$ time and $O(n)$ space.

,
Proof: Suppose that one of the intersections, whose number is at most , ofcorrespondis to a vertex on the minimum diagram in, and theandin,t-coordinate of this point is. There exists a point which is equidistant from$p_{j}(t’),$ $p_{k}(t’),$, and, for the other indices $h,$is farther fromthan these(for sufficiently small),
four points. For
is the end points of the leftest$E_{jk},$or rightest component of one of the sets
and. Suppose, thenis the end point of the leftest or rightest edge inis an intersecting
value of one of the functions
anddefined for the indicesand . Therefore, any vertex on the minimum diagram is associated with a intersecting,
value of one of the functions
or with a solution of one of theandequations $g^{+}+g^{-}=0,\tilde{g}^{+}+\tilde{g}^{-}=0$ and $g^{+}-\tilde{g}^{-}=0$ . When, then it isassociated with a solution of $g^{+}-\tilde{g}^{-}=0$ . Conversely, each of such intersecting values
corresponds to a unique vertex in the minimum diagram. A solution of $g^{+}-\tilde{g}^{-}=0$
corresponds to a vertex in the minimum diagram in the case that $g^{-}=+\infty,\tilde{g}^{+}=+\infty$
and $g^{+}=\tilde{g}^{-}=2r_{ij}$ .
Hence, the combinatorial complexity of the weighted dynamic Voronoi diagram is$O(n^{2}\lambda_{s+2}(n))$ . By computing,,,
for any pair ofand, all the vertices on the weighted Voronoi diagram can be listed in $O(n^{2}\lambda_{s+1}(n)\log n)$time and $O(n)$ space.
$f_{i},$$s$$f_{k}$$f_{l}$$E^{4}$$f_{j}$$E^{3}$$t’$$p_{i}(t’)$$q$$p_{h}(t’)$$p_{l}(t’)$$t’-t_{\epsilon}$$t_{\epsilon}$$q(t’-t_{\epsilon})$$E_{ik},$$E_{ij},$$q$$E_{il},$$q(t’-t_{\epsilon})$$t’$$E_{ij}$$g^{+},$$g^{-},$$E_{kl}$$E_{jl}$$h$$g’,\tilde{g}^{+},\tilde{g}^{-},\tilde{g}’$

$j$

$j$

$g^{+}$$g^{-},\tilde{g}^{+}$$\tilde{g}^{-},$$q=\overline{m}_{ij}$$g^{+},$$g^{-}$$g’$$\tilde{g}^{+},\tilde{g}^{-},\tilde{g}’$$h$$p_{i}(t)$$p_{j}(t)$$\square$

5. Conclusion
In this paper, we extend the concept of the weighted Voronoi diagram forpoints tothe one for the case that the coordinates of each point and the weights are represented bypolynomials or rational functions of a parameter. We show that combinatorial complexityof this dynamic Voronoi diagram iswhere is some fixed number determined$n$$O(n^{2}\lambda_{s}(n))$

$s$

119
is the maximum length of $(n, s)$ Davenportby the degree of the functions andSchinzel sequence. Since a lower bound of this dynamic Voronoi diagram can be shown, our bounds are tight within $\log^{*}n$ factor, which beats bounds within
to befactor.
Applications of these dynamic Voronoi diagrams to some generlized geometric fitting problems are also presented. As related problems, constructing the higher-order
Voronoi diagram for moving points in the plane and the dynamic Voronoi diagram forcircles in the Euclidean geometry and in the Laguerre geometry can be considered.
For these problems, using the same technique presented in this paper, we obtain an$O(n^{2}\lambda_{s+1}(n)\log n)$algorithm for moving circles in Euclidean and Laguerre geometry, andan $O(n^{2}m\lambda_{s+m+2}(n)\log n)$ algorithm for the dynamic m-th Voronoi diagram.
$\lambda_{s}(n)$$\Omega(n^{3})$$n^{\epsilon}$$n$References[1] P. K. Agarwal, M. Sharir and P. Shor: Sharp Upper and Lower Bounds for the Lengthof General Davenport-Schinzel Sequences. $Jo$ urnal of Combin atorial Theory, Series ,Vol. 52 (1989), pp.228-274.
[2] H. Aonuma, H. Imai, K. Imai and T. Tokuyama: Maximin Location of Convex Objects
in a Polygon and Related Dynamic Voronoi Diagrams. Proceedings of the 6th Annu $al$
$ACM$ Symposium on Computa tional Geometry, 1990, pp.225-234.
[3] M. J. Atallah: Some Dynamic Computational Geometry Problems. Computers andMathematics with Applica tions, Vol.11 (1985), pp.1171-1181.
[4] F. Aurenhammer and H. Edelsbrunner: An Optimal Algorithm for Constructing the
Weighted Voronoi Diagram in the Plane. Pattern Recognition, Vol. 17 (1984), pp.251$A$

257.

[5] L. P. Chew and K. Kedem: Placing the Largest Similar Copy of a Convex Polygon.
Proceedings of the 5 th Anuual $ACM$ Symposi um on Computational Geometry, 1989,
pp.167-174.
[6] H. Edelsbrunner, J. Pach, J. T. Schwartz and M. Sharir: On the Lower Envelope ofBivariate Functions and Its Applications. Proceedings of the 28th IEEE Annual Symposi um on Foundations of Compu $terS$ cien ce, 1987, pp.27-37.
Line Segments in $O(n\log n)$ Time.
[7] J. Hershberger: Finding the Upper Envelope ofInformation Processi $ng$ Letters.
[8] K. Imai: Voronoi Diagrams for Moving Points and its Applications (in Japanese). Tran sactions of the Japan Society for Industrial and Applied Mathematics, Vol. 1 (1991),
pp.127-134.
[9] K. Imai and H. Imai: Higher-Order Dynamic Voronoi Diagrams and its Applications(in Japanese). Memoirs of Ma thematical Research Institu $te,$ , Kyoto University, Vol.
790, 1992, pp.222-228.
[10] K. Imai, S. Sumino and H. Imai: Geometric Fitting of Two Corresponding Sets ofPoints. Proceedings of the 5th An uual $ACM$ Symposium on Computational Geometry,
1989, pp.266-275.
[11] J. T. Schwartz and M. Sharir: On the Two-Dimensional Davenport-Schinzel Problem.
$Jo$ urnal of Symbolic Computa tion, Vol.10 (1990), pp.371-393.
[12] E. Szem\’eredi: On a Problem by Davenport and Schinzel. Acta Arithmetica, Vol. 25(1974), pp.213-224.
$n$