BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1348
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Near-Quadratic Bounds for the $L_{1}$ Voronoi Diagram of Moving Points
AUTHOR:: Chew, L. Paul
DATE:: May 1993
PAGES:: 6
ABSTRACT::    
Given a set of $n$ moving points in the plane, how many topological changes 
occur in the Voronoi diagram of the points? If each point has constant 
velocity then there is an upper bound of $O(n^{3})$ [Guibas, Mitchell and 
Roos] and an easy lower bound of $\Omega(n^{2})$. It is widely believed that 
the true upper bound should be close to $O(n^{2})$. We show this belief to be 
true for the case of Voronoi diagrams based on the $L_{1}$ (or $L_{\infty}$) 
metric; the number of changes is shown to be $O(n^{2} \alpha (n))$ where 
$\alpha(n)$ grows so slowly it is effectively a small constant for all 
reasonable values of $n$.
END:: CORNELLCS//TR93-1348
BODY::
Near-Quadratic Bounds for the
L1 Voronol Diagram of Moving Points
L. Paul Chew*
TR 93-1348
May1993
Department of Computer Science
Cornell University
Ithaca NY 14853-7501
Whis woi?k was supported by the Advanced Research Projects Agency of the
Department of Defense under ONR Contract N00014-92-J-1989, and by ONR
Contract N00014-92-J-1839, NSF Contract lRI-9006137, and AFOSR Contract
AFOSR-91 -0328.
L1
Near-Quadratic Bounds for the
Voronoi Diagram of Moving Points
L. Paul Chew *
Department of Computer Science
Cornell University
Ithaca, NY 14853
April 30,1993
Abstract
Given a set of n moving points in the plane, how many topological changes occur
in the Voronoi diagram of the points? ff each point has constant velocity then there
is an upper bound of 0(n3) [Guibas, Mitchell, and Roos] and an easy lower bound of
?(n2). It is widely believed that the true upper bound should be close to 0(n2). We
show this belief to be true for the case of Voronoi diagrams based on the L1 (or L?)
metric; the number of changes is shown to be 0(n2o(n)) where 0(n) grows so slowly
it is effectively a small constant for all reasonable values of n.
1 Introduction
Suppose we have a set of points in the plane, each point moving with its own, constant
velocity. Consider the Voronoi diagram of the points; this diagram moves continuously as
the points move, but distinct topological changes occur when 4 points become cocircular.
The question we address is: How many such topological changes can occur? For constant-
velocity points in the plane, it is widely suspected that the number of topological changes
in the Voronoi diagram is near 0(n2). This suspicion is presently supported by a lack
of counterexamples rather than a proof; the best lower bound is currently ?(n2) which
can be achieved by two lines of points passing each other in opposite directions as if on a
roadway. The best upper bound is currently 0(n3) [GMR91], proved using the technique
of linearization. In this paper we show that for Voronoi digrams based on the L1 (or L?)
metric, the bound on the number of topological changes as the source points move is near
0(n2), namely 0(n2o(n)) where o is the very slowly growing inverse Ackermaun's flinction.
*This work was supported by the Advanced Research Projects Agency of the Department of Defense under
ONR Contract N00014-92-J-1989, and by ONR Contract N00014-92-J-1839, NSF Contract IRI-9006137, and
AFOSR Contract AFOSR-91-0328.
0
F
L
Figure 1: A corner edge and a noncorner edge.
0
The technique used here is related to a technique used by the author and K. Kedem in
[CK89, CK93] where a type of Voronoi diagram is used for placing a convex object among
polygonal obstacles. The number of topological changes that occur in a convex-distance-
function-based Voronoi diagram as the distance defining shape (a convex polygon with k
sides) is rotated was shown to be O(k4n2o(n)).
In some ways it is more natural to work with the Delaunay trnangulatzon, the dual of the
Voronoi diagram. Topological changes in the Voronoi diagram correspond to edge flips in the
Delaunay triangulation. Adjacencies in the Delaunay triangulation remain fixed except at
distinct events when the four points of two adjacent Delaunay triangles become cocircular.
Given a set of moving points, the number of changes that occur in the Delaunay trian-
gulation appears to be closely related to the problem of counting the number of changes
that can occur in the Minimum Spanning Tree (MST), since it is well known that the MST
is a subgraph of the Delaunay triangulation. However, there are changes in the MST that
do not correspond to changes in the Delaunay triangulation --H edge lengths in the Delaunay
triangulation can change enough to alter the MST without causing a change in the Delaunay
triangulation. Katoh, Tokuyama, and Iwano [KT192] have shown that for the L1 (or L?)
distance and for n points, each moving at constant velocity, the MST undergoes O(fl25?(n))
changes.
2 Counting Corner Edge Changes
We assume the reader is familiar with Delaunay triangulations. In particular, we make use
of the fact that for each edge of the Delaunay triangulation there is an empty circle that
goes through the endpoints of the edge. For the L? metric, the circlethat we use is actually
a square. For the L1 metric, the circle is a square tipped at 45 degrees. For our problem
the L1 and the L? metric are equivalent since only the shape matters. For the remainder of
this paper, we use the L? metric since it is easier to draw squares that are not tipped.
We distinguish two types of Delaunay edges: corner edges and noncorner edges (see
Figure 1). A Delaunay edge is called a corner edge if there exists an empty square through
the endpoints of the edge with a corner of the square on one of the endpoints. The remaining
Delaunay edges are called noncorner edges. Note that since an empty square placed on an
edge can slide while remaining in contact with the edge's endpoints, a Delaunay edge is a
2
t
Figure 2: The closer hit corresponds to a corner edge.
noncorner edge only if the sliding is blocked by other source points (see Figure 1) --H otherwise
the square could slide far enough to show that the edge is really a corner edge. Each noncorner
edge has a pair of these blocking points.
Our goal is to determine the number of changes in the Delaunay triangulation as the
source points move. Any change in the Delaunay triangulation is a change in either a corner
edge or a noncorner edge. If we can determine a bound on these edge changes then we also
have a bound on the total number of Delaunay triangulation changes. We start by bounding
the number of changes for corner edges.
Theorem 1 For n points, each moving with constant velocity, there are O(n2?(n)) changes
in the set of corner edges.
Proof: We show that for each source point p, there are O(n?(n)) changes in its corner
edges. We then sum over all points to get the bound in the theorem. Note that there are
four types of corner edges corresponding to the four corners of the square. Without loss of
generality, we consider just the corner edges corresponding to the lower left corner of the
square.
At a fixed time t, we can find the corner edge for source point p by placing a very small
square with its lower left corner on p. We then grow the square until it hits some other
source point. This first point that we hit (assuming we hit something at all) determines
the current corner edge for p. We recast this view of corner edges to use triangles instead
of a square. We split the square into two triangles (see Figure 2). Think of placing both
triangles on our source point p, then expanding each of them independently until they each
hit a source point. The closer of the (at most) two hits determines the corner edge for p.
Now consider just one of the two triangles, say the top one. For each source point q (# p),
we create a copy of the triangle and place the lower corner of the triangle on p and expand
the triangle until it touches q. We associate a value with each source point q; the value for q
is the size of the resulting triangle (measured as the length of the triangle's hypotenuse, for
instance). Note that for many source points the expanding triangle does not ever hit them
so the associated value is infinity.
As time progresses, the value associated with q changes, so we have a function on t for
each q. Note that, for an individual point q, the corresponding function looks like a line
segment. The endpoints occur because q can enter and leave the zone where the expanding
3
e
Figure 3: For each noncorner edge e, the endpoints of e and the two blocking points form a
cell of four corner edges.
triangle can touch it. Wfthin this valid zone, the function is linear since q travels with
constant velocity with respect to ?. Thus, if we plot triangle size for each point q over time,
the result looks like a set of at most n line segments. We get a similar set of line segments
for the other, lower triangle.
Recall that the corner edge for p corresponds to the first hit we get as we expand the
two triangles. In other words, the corner edge for p corresponds to the lower envelope of the
combined set of segments from both of the triangles. A change in the corner edge corresponds
to a break-point in the lower envelope. The lower envelope for a set of 0(n) line segments
is of complexity O(nQ(n)) [ASs89J, so there are at most that many changes in the corner
edges for point p. The bound in the theorem follows by summing these changes over all four
corners of the square and over all points p. ?
3 Counting Noncorner Edge Changes
Recall that each change in the Delaunay triangulation corresponds to a change in either a
corner edge or a noncorner edge. Now that we have a bound on changes for corner edges,
changes for noncorner edges are relatively easy to count.
We claim that each noncorner edge of the Delaunay triangulation exists in a cell consisting
of four corner edges. This follows from the earlier observation that, for a noncorner edge, an
empty square placed on the edge is blocked from sliding too far by other source points. Once
we slide the square against one of these blocking points, it is easy to see that the square can
be shrunk to confirm the existence of two corner edges for each blocking point (see Figure
3).
Within the lifetime of a single cell (a quadrilateral) there can be just 0(1) swaps of its
two diagonals. This is because, with constant velocity points, a set of four points becomes
cocircular at most a constant number of times. In total there are O(n2?(n)) cells: 0(n) of
them existing at time zero and, by Theorem 1, 0(n2o(n)) new ones that occur over time as
corner edges change. Thus, we have the following theorem:
Theorem 2 For a set of n points, each moving with constant velocity, there are 0(n2?(n))
changes in the L? (or L1) Delaunay triangulation of the point set. The same bound holds
4
for the number of topological changes in the corresponding Voronoi diagram.
4 Discussion
The technique outlined above can be generalized in several ways:
0
0
0
0
The technique applies to more than just L1 and L? distances; it applies to any convew
distance function where the distance-defining convex shape is a polygon. (For addi-
tional information on convex distance functions and their relation to Voronoi diagrams
and Delaunay triangulations see, for instance, [CD85J or the survey [Aur9i].) The
above technique can be used to show that, for n points, each moving with constant
velocity, and for a Delaunay triangulation based on a convex distance function deter-
mined by a k-sided convex polygon, there are O(k4n2?(n)) changes in the Delaunay
triangulation. I suspect there are too many factors of k in this bound.
Similar, near-quadratic bounds hold for more complex motions of the source points
provided that motion of the points is restricted so that no four points become cocir-
cular more than a constant number of times. Note that cocircular here refers to a
nonstandard circle.
Near-quadratic bounds also hold when we use sources more complicated than points.
For instance, the sources might be moving rectangles or moving polygons. Techniques
are relatively straightforward for polygonal sources that do not rotate and that move
in straight lines. Motions that are more complex would have to be restricted to avoid
groups of repeatedly cocircular points. See [CK89, CK93] for the definition of the
appropriate edge Delaunay trnangulation and for a partial indication of how more-
complex sources could be handled.
The results presented here can be used to derive a bound on the complexity of moving
a (nonrotating) convex polygon among moving obstacles. The use of a type of Voronoi
diagram for motion planning is discussed in [CK93J which includes references to earlier,
related work.
The work presented here was originally started as part of an attempt to close the com-
plexity gap for changes in the standard Delaunay triangulation of n constant-velocity points.
As mentioned in the Introduction, the current lower bound is ?(n2) while the current upper
bound is 0(n3). It may be that the techniques presented here will at some point be useful
in closing this gap; unfortunately though, there are major differences in the behavior of the
standard Delaunay triangulation versus the L1 Delaunay triangulation. As an example, for
an individual source point p among n moving points, our results for L1 show that there are
O(n?(n)) changes that can take place in edges that touch p, while for the standard Delaunay
triangulation there can be ?(n2) changes.
5
References
[ASS89j
P. K. Agarwal, M. Sharir, and P Shor, Sharp Upper and Lower Bounds on
the Length of General Davenport-Schinzel Sequences, J. Combinatorial Theory,
Series A, 52 (1989), 228-274.
[Aur91] F. Aurenhammer, Voronoi Diagrams --H a Survey of a Fundamental Geometric
Data Structure, ACM Computing Surveys, 23 (1991), 345-405.
[CD85]
[CK89]
[CK93]
[GMR91]
L. P. Chew and R. L. Drysdale, Voronoi Diagrams Based on Convex Distance
Functions, Proceedings of the First Annual Symposium on Computational Geom-
etry (1985), ACM Press, 235-244.
L. P. Chew and K. Kedem, Placing the Largest Similar Copy of a Convex Polygon
among Polygonal Obstacles, Proceedings of the Fifth Symposium on Computa-
tional Geometry (1989), ACM Press, 167-174.
L. P. Chew and K. Kedem, A Convex Polygon Among Polygonal Obstacles:
Placement and High-Clearance Motion, Computational Geometry: Theory and
Applications, to appear.
L. Guibas, J. Mitchell, and T. Roos, Voronoi Diagrams of Moving Points in the
Plane, Graph-Theoretic Concepts in Computer Science, 1991 Proceedings, LNCS
570, editors G. Schmidt and R. Berghammer, Springer-Verlag, 1992, 113-125.
N. Katoh, T. Tokuyama, and K. Iwano, On the Minimum and Maximum Span-
ning Trees of Linearly Moving Points, Proceedings of the 33rd Annual IEEE
Symposium on the Foundations of Computer Science (1992), IEEE Computer
Society Press, 396-405.
6
[KT192]
