BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR94-1441
ENTRY:: 1994-08-26
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Lower bounds for the complexity of the Hausdorff distance
AUTHOR:: Rucklidge, William J. 
DATE:: August 1994
PAGES:: 20
ABSTRACT::
The Hausdorff distance is a similarity measure defined between sets in
the plane.  Algorithms to find the minimum distance as one set is
transformed have been described, but few lower bounds are known.  We
describe new lower bounds for the complexity of the directed
Hausddorff distance.  We exhibit lower boundconstructions for both
sets of points and sets of points and line segments, under
translation, rigid motion, translation and scaling, and affine
transformation.  The results for point sets can also be extended to
the undirected Hausdorff distance.  As these lower bounds are for the
complexity of the graph of the Hausdorff distance as a function of
transformation, they do not necessarily bound functions which search
this graph, but do give an indication of how complex the search may be.
END:: CORNELLCS//TR94-1441
BODY::
Lower Bounds for the Complexity of the
Hausdorff Distance
William J. Rucklidge
TR 94-1441
August 1994
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
Lower bounds for the complexity of the Hausdorff
distance
William J Rucklidge
Department of Computer Science, Cornell University
Ithaca NY 14853, USA
wjr?cs.cornell.edu
Abstract
The Hausdorff distance is a similarity measure defined between sets in the plane.
Algorithms to find the minimum distance as one set is transformed have been described,
but few lower bounds are known. We describe new lower bounds for the complexity of
the directed Hausdorff distance. We exhibit lower bound constructions for both sets of
points and sets of points and line segments, under translation, rigid motion, translation
and scaling, and affine transformation. The results for point sets can also be extended
to the undirected Hausdorff distance. As these lower bounds are for the complexity
of the graph of the Hausdorff distance as a function of transformation, they do not
necessarily bound functions which search this graph, but do give an indication of how
complex the search may be.
1 Introduction
The llausdorff distance between two sets A and B is defined as
H(A, B) = max(h(A, B), h(B, A))
where
h(A,B) = 5???PI?4 Ia--H bil
some Lp norm). In this paper, A and B will
finite number of points or a finite number of
and is some norm (here restricted to be
be subsets of the plane consisting of either a
points and non-intersecting line segments.
h(A, B) is called the directedllausdorff distance from the set A to the set B. H(A, B) is
the undirected llausdorff distance between the sets A and B. h(A, B) will be small exactly
when every point in A is close to some point in B; h(B, A) will be small when every point
in I? is close to some point in A, and H(A, B) will be small when both of these are true. In
particular, h(B, A) < eexactly when for any bE Bthere is some a ? A such that Ila--Hbli ?
Let A? = A ? D(e) where D(e) is the "disk" of radius E (the set of all points x such that
lixil < E) and e is the Minkowski sum. A key observation is that h(B, A) ? E iff B c AE.
In many problems, we want to determine the transformation of one set which brings it
into closest correspondence with the other set, Let G be some group of transformations.
Then for any 9 c G define
DG(9)			H(A,9(B)).
In other words, we transform the set B by some transformation 9 and compute the Hausdorff
distance between this transformed set and A. This defines a function of 9, and we wish to
determine the minimum value of this function, as the transformation which gives rise to
this minimum value will be the one bringing B into closest correspondence with A. Many
approaches to determining this minimising transformation are based on searching the graph
of this function (for example, by enumerating the local minima, as in [5]). It is therefore of
interest to know what the geometric complexity of this graph may be. Upper bounds have
been determined for some transformation groups, but few lower bounds were known. We
will also be considering the graph of the function
dG(9) = h(g(B), A)
which is the graph of the directed distance from the transformed set 9(B) to A.
We will exhibit lower bounds for the complexity of such graphs as follows. The con-
structions presented below are all parameterised by two values, e and n (and possibly other
parameters). For each problem, we will fix some values for t and n (and possibly other param-
eters), and construct sets A and 1? having km elements each, for some constant k depending
on the problem. We will then show that the set [9 dG(9) ? ?? has ?((kn)') = ?(n') com-
plexity, for some constant 1 depending on the problem. We do this by showing that this set
has ?(n') distinct connected components. Since each one must contain some local minimum
of dG(g), this shows that there are ?(nt) local minima in the graph of dG(9). In some cases,
we also show that the graph of Dc(g) may have this complexity. Previous constructions,
such as those in [4], have been for the directed llausdorff distance alone.
We also show that the constructions for the undirected llausdorff distance and the con-
structions for the directed distance on which they are based may have high complexity in a
small space: for a fixed E, we can make DG(9) have ?(n') complexity in an arbitrarily small
region of transformation space (i.e. this does not depend on just shrinking t). This is moti-
vated by the observations in [2] and [7] that for some groups G, if DG(g) ? e, then 9 must lie
in a small region in transformation space. If the undirected Hausdorff distance could have
only small complexity in a small area, even though it might have high complexity overall,
we might be able to obtain efficient algorithms, as was done in [7]: the global minimum of
DG(9) would be restricted to lie in a small area, and searching only this area of its graph
would take less time than searching the entire graph. The lower bounds here show that, in
some cases, this is not possible.
Table 1 shows the problems for which we present lower bounds; Table 2 shows the running
times of the algorithms which solve those problems. It can be seen that in most cases, the
running times are nearly tight with the lower bounds. The exception is the bound for point
sets under translation with the L1 and L? norms in [4], where an algorithm was given which
uses the structure of the problem under these norms to avoid explicitly searching the entire
graph. It may be possible to develop algorithms using similar techniques for some of the
other problems, and so it should be emphasised that the lower bounds presented here are
2
Table 1: Results for the complexity of the llausdorff distance between two sets of size n. All
the lower bound results for point sets are for the undirected Hausdorff distance, and all of the
results for sets of points and nonintersecting line segments are for the directed distance. The
results for the undirected distance also show that this complexity can occur in arbitrarily
small space.
Problem			Lower Bound
Transformation			Set type			Norm			Complexity
Translation			Point Sets			L1, L2, L?			?(n )
Points and Segments			Any Lp			?(n )
Rigid Motion			Point Sets			L2			Q(n )
Points and Segments			L2			?(n )
Translation and			Point Sets			L1, L2, L?			?(n )
y scale			Points and Segments			Any Lp			?(n )
Affine			Point Sets			L1, L2, L?
Transformations Points and Segments			Any Lp			?(m )
Table 2: Upper bounds for finding the exact minimum Hausdorff distance under transfor-
mation between two sets of size n.
Problem			Solution
Transformation			Set type			Norm			Complexity
Translation			Point Sets			L1, L? O(n2 log n) [4]
L2			O(n logn) [5
Points and Segments L1, L?			O(n oL(n)) [5]
L2			O(n log			n)			[1]
Rigid Motion			Point Sets			L2			O(n5 log			n)			[3]
Points and Segments			L2			O(n log			n)			[3]
for the complexity of the graph of the llausdorff distance, and do not necessarily give lower
bounds for algorithms to determine the optimal transformation.
In this chapter, we will be dealing with four transformation groups: the group T of
translations, the group R of rigid motions (translations and rotations), the group S of trans-
lations and (x, y) scaling, and the group A of nondegenerate affine transformations. Let t be
a translation and 0 an angle. Define
DT(t)			H(A,B?t)			(1)
dT(t)			=			h(B 0 t, A)			(2)
DR(t,O)			=			H(A,re(B) ot)			(3)
dR(t, 0)			=			h(re(B) 0 t, A)			(4)
Ds(t, 8x, s?)			=			H(A, Ss,%(B) 0 t)			(5)
ds(t, Sx, s?)			=			h(Se?%(B) 0 t, A)			(6)
3
DA(t, M) = H(A, M(B) e t)			(7)
dA(t, M) = h(M(B) ? t, A)			(8)
where
o+ r?(B) denotes the set obtained by rotating B by 0 counterclockwise about the origin,
o+ Ss?s?(B) denotes the set t(s?x,s??) I (x,y) E B? (i.e. the set obtained by scaling B by
a factor of ?z in the x direction and s? in the ? direction),
o+ M represents a non-singular 2 x 2 matrix, and
o+ M(B) denotes the set ?Mb b ? B? (i.e. the result of applying M to every point in B).
2 Point sets under translation
This section describes two constructions of point sets A and B, each containing 0(n) points,
for which the function DT(t) has ?(n3) local minima within an arbitrarily small area. The
first construction is for the L1 or L? norm; the second is for the L2 norm.
2.1 The L1 and L? example
We use the L? norm throughout; rotating the point sets by 450 gives the construction for
L1.
Let A consist of two diagonal rows, each of n points spaced a apart (i.e. a apart in both
x and y). The rows are 2? t 6 apart, where 6 < a/n. A and A? are shown in Figure 1. The
area left uncovered by A? contains a ?` of ?(n) steps, in the gap between the two
sides. The width of this gap is 6. Note that by reducing a, the two rows can be compressed
inwards, thereby making the stairsteps (and thus the total length of the staircase) as small
as desired. This is shown in Figure 2.
Let B consist of two diagonal rows of points, each of n points, as shown in Figure 3. The
points in each row are slightly more than 6 apart, and are placed so that one row lies around
the horizontal part of a stairstep, and the other lies around the adjacent vertical part. Since
the stairstep lengths are all a, and 6 < a/n, we can make each row of B shorter (in height
and width) than a stairstep segment.
Consider translating B slightly upwards or downwards. The points around the vertical
stairstep will remain inside A? or outside it, as they were before, but the points around the
horizontal stairstep will move into and out of A? as B moves. Similarly, as B moves left
or right, the points around the vertical stairstep will move in and out of AE, but the points
around the horizontal stairstep will not. We can thus see ?(n2) different configurations of B
with respect to this one stairstep, since we can independently choose where the gaps lie in
the two rows of B. B can also be translated so that it straddles any of the other stairsteps,
each of which gives rise to ?(n2) configurations, for a total of ?(n3) configurations.
Each one of these configurations can be labelled with three numbers from 1 to n --H 1:
the number of points in the bottom row of B that are to the left of (or above) the gap, the
4
a
Figure 1: The sets A and A? for the L? lower bound for point sets under translation.
Figure 2: An illustration of the effect of reducing a.
5
Figure 3: The sets AE and B for the L? lower bound for point sets under translation.
number of points in the top row of B that are to the left of the gap, and the number of the
stairstep which is straddled by B. We will only consider configurations where there is at
least one point of each row of B on either side of the gap. ?(n3) such labels are possible.
Suppose t1 and t2 are translations representing configurations with distinct labels. Then
dT(tl) < e and dT(t2) < E but any path from t1 to t2 must pass through a translation t
where dT(t) > ?: either some point in one of the rows of B must cross the gap, in which
case dT(t) > ? when t is a translation placing that point inside the gap, or B must be moved
so as to straddle another stairstep, in which case again at least one point of B must move
through the gap. All these labels therefore label distinct regions.
Another way to visualise this is similar to that used in [4]: define S(A, E, b) for some
b ? B to be A? ? --Hb. Then t ? S(A, e, b) exactly when b + t ? A?. This set is therefore the
set of all translations which map b into A?. Now define S(A, ?, = flbEBS(A, c, b). Then
t E S(A, E, B) iff B ? t c AE, or DT(t) ? E; S(A, E, B) is therefore the set of all translations
t which make h(A, B ? t) <?.
We can construct S(A, ?, B) by making a copy of AE for every point in B, translating
these copies and forming their intersection. Alternately, we can consider making a copy of
the complement of A? for every point in B, translating these copies, and forming their union.
This union will have a "hole" for every connected component of S(A, e, B). Figure 4 shows
such a union. Each jagged line represents the "gap" staircase of some translation of A? (i.e.
portions of one copy of the complement of A?). There are two sets of translations of this
staircase, corresponding to the two rows of B. There are other parts of the complement of
AE which have not been drawn here, but they do not affect the ?(n3) holes shown here.
We now note that 6 can be made as small as desired, thereby narrowing the staircase
gap and reducing the lengths of the rows of B, and the staircase itself can be compressed as
much as is desired by reducing a (as long as 6 stays smaller than a/n). This means that,
for a fixed n and E, we can compress the ?(n3)-complexity region down into an arbitrarily
small area, bounded by a square ma on each side, since that is the length of the staircase.
We would also like to show that the area where the undirected llausdorff distance DT(t)
is no greater than E can also have large complexity in a small space. This can be done by
augmenting B so that h(A, B ? t) ? ? in the entire region of interest. We set a < e/n so
6
Figure 4; An illustration of s(A, ?, B) for the L? lower bound for point sets under translation.
that the rows of A have length less than e, and add two points to B, one in the middle of
each row of A. Then if the main body of B is translated anywhere on the staircase, these
two extra points remain within (or close to) the rows of A. Since the rows have length less
than t, there is always some point of B within e of any point of A, for any translation in the
complex region. Thus, H(A, B ? t) > E exactly where h(B ? t, A) > ? (at least in this region
of interest), since h(A, B e t) will always be at most E. The undirected Hausdorff distance
DT(t) therefore has complexity ?(n3). The region containing this complexity can be made
arbitrarily small.
2.2 The L2 example
In this subsection, we show how the previous example can be modified so that it works with
the L2 norm. Here, A again consists of two vertical rows of n points. The points in each row
are spaced a apart and the rows are staggered by a/2 (see Figure 5). The rows are slightly
less than 2e apart, so that the circles of A? are ? apart at their closest approach. The gap
between the left and right sides is not of constant width and has a complicated shape.
The set B again consists of two rows of n points. These rows are horizontal, and spaced
a/2 apart. The points in each row are slightly more than 2? apart. They are shown super-
imposed on AE in Figure 6. The idea is that, no matter what values a, 6 and n have, if 6
is small enough, then it is possible to choose n1 and n2 independently, and position B such
that B C A?, there are n1 points of the top row on the left side of the gap, and n2 points of
7
c'/2t
Figure 5: The sets A and A' for the L2 lower bound for point sets under translation.
a
the bottom row on the left side of the gap. This would give ?(n2) possible configurations of
B around a single "wobble" in the gap; as there are ?(n) such "wobbles", there would be
?(n3) different configurations of B with B c A'. A labelling argument, similar to that in
the previous subsection, shows that these configurations are all distinct.
This is difficult to visualise, so again we will look at S(A, e, B). We will construct this,
as before, by taking the union of 0(n) copies of the gap, translated by various amounts, and
showing that the complement of this union has ?(n3) disjoint connected components.
Since the actual gap has such a complicated shape, we will deal only with a small part
of it. In particular, we will consider only the regions where the gap's width is between 6
and 26 (recall that 6 is the width of the narrowest part of the gap). There are Q(n) regions
where this is true, each one centred around a place where the gap is at its narrowest. We
bound each such region by a rectangle. These rectangles will be 26 wide by A long, where A
is determined by c and 6, and is equal to #m?62. See Figure 7 for an illustration of this
region. Now, note that A/6 = 7m6--H1. Thus, for any fixed E, we can make A/6 as large as
we like by making 6 small enough. This means that the interesting sections of the gap can
be made arbitrarily "skinny": as 6 decreases, the rectangles get narrower and shorter, but
their length to width ratio (i.e. A/(26)) increases.
The gap is narrowest exactly where a line from one point in the left row of A to one of its
neighbours in the right row crosses it. The interesting rectangles are oriented perpendicular
to such lines. There are two sets of such rectangles, one "leaning to the left" and the other
"leaning to the right". The angle between these two sets decreases as a decreases, but is
not significantly affected by 6. Suppose that we take n right-leaning rectangles, and position
8
Figure 6: The sets AE and B for the L2 lower bound for point sets under translation.
6
Figure 7: A closeup of the interesting region of the gap.
9
1ff
IL
IL
IL
IL
IL
1ff
Figure 8: An illustration of portions of S(A, E, B) for the L2 lower bound for point sets under
translation. Note the ?(n3) holes in the arrangement.
them slightly more than 26 apart (the same spacing as the points of B), so that the right
edge of one rectangle just touches the left edge of the next. We want to make 6 small enough,
and thus make the rectangles skinny enough, so that one left-leaning rectangle can intersect
all n of these right-leaning rectangles. This can be achieved by making 6 small enough that
A/6 is large.
In constructing S(A, ?, B), we will be making n copies of the gap stacked slightly more
than 26 apart (corresponding to one of the rows of B), and having these intersect with another
n copies, shifted down by a/2 (corresponding to the other row), giving 0(n3) intersections:
each left-leaning rectangle from one of the copies intersects n right-leaning rectangles from
other copies, and vice versa. Figure 8 shows such an arrangement. In terms of B and A,
this means that, as in Subsection 2.1, we can independently choose n1 and n2, and position
B in such a way that n1 points from its top row lie in the left half of A?, and n2 points
from its bottom row lie in the left half. There are ?(n) such placements for any ni and n2
(I < n1, n2 < n), one around each "wobble" of the gap, for ?(n3) different configurations.
Going from some configuration to another with a different n1 or n2 would involve some point
crossing the gap. Also, since the points of B are spaced about 26 apart and the gap becomes
wider than this between two adjacent "wobbles", and all of these configurations have at least
one point on either side of the gap, it is impossible to translate B from one configuration
to another with the same n1 and n2 without some point moving outside AE. Thus, all these
?(n3) configurations all belong to different connected components of S(A, ?,
Since A is a function of 6 and e, given values for n, t and a, we can find a value for 6
such that there are ?(n3) distinct regions in translation space where dT(t) ? t. These all
are contained in an area which is O(na) high by O(n6) wide, and so by a suitable choice of
10
Figure 9: The sets A, AE and B for points and segments under translation.
a, this region of high complexity can be made arbitrarily small.
As in Subsection 2.1, if na < ?, we may augment B by two points, one each in the middle
of the two rows of A, such that h(A, B ? ? E for all translations in the complex region;
this construction therefore similarly shows that the undirected llausdorff distance can have
large complexity in a small area.
3 Sets of points and line segments under translation
This section describes a construction of two sets A and B, each consisting of 0(n) points
and nonintersecting line segments, for which the graph of the function dT(t) = h(B ? t, A)
has ?(n?) complexity.
Fix ? and n and let 6 < e/n. Now let A consist of a group of n horizontal segments, each
of length (n --H 1)(2? t 6), spaced 2e t 6 apart, plus a similar group of n vertical segments. A?
then consists of n horizontal bars and n vertical bars, with gaps of width 6 between adjacent
bars. Note that this is true for any Lp norm: the caps on the ends of the bars have different
shapes for different norms, but the main lengths of the gaps between the bars have the same
shapes. Now, let B consist of a vertical row of n points, spaced 26 apart, located at the
bottom-left corner of the group of horizontal lines in A, plus a similar horizontal row located
at the bottom?left corner of the group of vertical lines. Figure 9 shows B overlaid on A and
AE.
There are ?(n?) different configurations of B with respect to A: the vertical row of B can
be placed in any one of ?(n2) different configurations with respect to the horizontal segments
of A, as it can be straddling any of the n --H1 gaps, and from 1 to n--H1 points can lie below the
gap; similarly, the horizontal row can be placed in any one of ?(n2) different configurations
with respect to the vertical segments of A. Note that sliding B horizontally does not affect
the configuration of the vertical row, and sliding it vertically does not affect the configuration
of the horizontal row (as long as these rows remain within limits); the configurations of the
two rows may thus be chosen independently, for a total of ?(n?) different configurations.
These are all clearly distinct, since any two differ in the number of points of B contained in
one of the connected components of A?, so any path from one configuration to another must
11
Figure 10: The sets A2 and A2? for point sets under rigid motion.
contain a translation of 1? where some point is crossing some gap.
4 Point sets under rigid motion
We will use the L2 norm wherever we deal with rotation, since it is the only rotationally
symmetric Lp norm.
The following construction shows that there can be ?(n5) distinct connected components
where the undirected Hausdorff distance DR(t, 0) between two sets of ?(n) points is less
than E, in an arbitrarily small region in (t, 0) space. It is based on an augmentation of A and
1? from Subsection 2.2. For clarity, we will (both here and below) refer to the sets A and B
constructed for the translational lower bounds as AT and BT.
First, note that it is possible to rotate BT from that construction by some very small
angle 0min about its centroid while still maintaining the ?(n3) complexity of h(BT ? t, AT).
This is because there must be, in the ?(n3) arrangement of connected components, some
minimum distance between features, and so any rotation which does not move any feature
of the arrangement more than half this distance cannot change the overall topology of the
arrangement: none of the connected components merge, nor do any vanish.
The augmentation to AT consists of n points along a vertical line, spaced less than ?/(2n)
apart. If we put a disk of radius E about each, we will have a shape with two "scalloped"
edges, as shown in Figure 10. We will refer to this row of points as A2.
Now, if A2 is located sufficiently far away from the centre of rotation, and perpendicular
to the line joining it to the centre of rotation, then it is possible to pass a circular arc (centred
at the centre of rotation) through the inner scalloped edge so that it passes through each of
the n lobes and the gaps between them. It will not pass through these lobes evenly: it will
cut deeper into some of them than others. However, by moving the row farther away and
thus increasing the radius of the arc, we may control the magnitude of this effect, since the
arc approaches a straight line as A2 moves away. By slightly adjusting the radius of the arc,
12
?1
w
Figure 11: The interaction between A2E and B2.
we may also control the ratio between the arc length contained inside the lobes and the arc
length contained in the spaces between the lobes. We will place A2 far enough away and
position the circular arc such that the ratio between the arc length contained in any lobe
and the arc length contained in the space next to that lobe is greater than 8n :1. Let the
shortest of the arc lengths contained in the lobes be 1, and the smallest depth of any of the
gaps be w (see Figure 11). As the arc becomes closer to a straight line (as A2 is moved away
from the centre of rotation), the lengths of the arc segments contained in the lobes become
more similar (and, at the limit, are all equal). A2 should be positioned far enough away that
they are all within a factor of two of each other. The widest gap is then smaller than 1/(4n).
We now construct B2, which consists of n points positioned l/(2n) apart along this
circular arc, initially located in the lowest lobe of A2E. We also add an extra point to B2;
this point is initially located at the lower end of A2. Now, as R2 rotates about the centre
of rotation, this row of points will move along this circular arc. Since the spaces between
lobes along this path are all less than l/(4n) across, and the entire arc of points will fit into
a single lobe, only one point will be passing through a gap at a time, and there will be ?(n2)
different configurations of B2 with respect to this part of A2E: there are n --H 1 gaps to be
straddled, and for each gap, between 1 and n --H 1 points of B2 can be above the gap. Note
that all of these configurations have the property that all of the points of A2 are within t of
some point of B2, specifically the extra point.
Pick 6 such that the points of B2 are straddling one of the spaces between lobes, and
such that this straddling is "even": the two points closest to the gap are equal distances
away from the edges of the gap. They will be at least 1/(8n) away from these edges. Now,
consider translating the points of B2 vertically up or down by up to l/(16n). If the arc along
13
d ?
Figure 12: The minimum depth of the points of B2.
which the points lie is close enough to a straight vertical line, then they will stay inside A2?.
Let d be the minimum horizontal "depth" achieved for any point of B2 at any point in this
translational range. Figure 12 shows this situation; the vertical bars are l/(8n) high (l/16n
above and below the centre). Now, let dmin be the smallest such d value achieved for any of
the ?(n2) possible such straddling configurations.
We now construct AT and 1?T as in Subsection 2.2 so that the ?(n3) complexity region
of DT(t) is smaller than l/(16n) high by min(dmin/2, w/2) wide, and so that the centroid of
B is at the centre of rotation. Let A = AT u A2 and B = BT U B2. Let 0 produce one of
the straddling configurations described above. Then, if 101 < 0min, there are ?(n3) different
connected components in t space where DR(t, 0) ? E. This is because a slight translation of
B2 with respect to A2 will not move any of the points of B2 out of A?2, and BT and AT have
been constructed so that the range of translations required is very small. Note that DR(t, 0)
will be determined by dR(t, 0) for all transformations in the range under consideration, as
the directed distance from A to the rotated and translated B will always be less than E.
A labelling argument similar to that in Subsection 2.1 now shows that there are
different connected components in (t, 0) space where DR(t, 0) < ?, Q(n3) corresponding to
each of the ?(n2) such values of 0. A key point in the argument is that it is not possible for
one of the points of B2 to "sneak around" the space between the lobes (through the main
body of A2E), since it would have to translate at least w away from the original circular arc,
which would force at least one point of BT to cross some gap. Thus, any two configurations
which differ in how the points of B2 are straddling the gaps of A2E must belong to different
connected components. Further, by reducing a and 6, and by moving A2 and B2 farther out,
we can make the region in (t, 0) space in which these connected components lie arbitrarily
small.
There is a problem with this construction as it has been presented: A2 must subtend an
angle of less than 0min, which depends on a and 6, which depend on 1 and w, which depend
14
Di
Dy
Figure 13: The sets A, A? and B for points and segments under rigid motion.
on the circular arc along which B2 is placed, which must have a larger radius for a smaller
0min and thus depends on 0min; the parameters are thus interdependent. However, as A2 and
B2 are moved farther out, 1 and w approach limit values, as the circular arc becomes closer
to a straight line. Thus, we can initially place A2 and B2 where 1 and w are within some
small factor (say, within 1%) of their limit values, then determine a and ? which work for any
values of 1 and w between their original values and their limit values, and thus determine
Omin This will give us a minimum value for the radius of the circular arc, and we know
that we can move A2 and B2 out farther if necessary without affecting the validity of the
construction.
5 Sets of points and line segments under rigid motion
This example is a modification of the example from Section 3, using the techniques from
Section 4. Again, we will refer to the sets A and B constructed in Subsection 3 as AT and
BT. As above, we observe that the set BT may be rotated by some small angle 0min about
its centroid without changing the topology of the arrangement.
Define the centre of rotation to be the centroid of BT. We augment AT by a group of
segments A2 identical to the left-hand group of AT, as shown in Figure 9. A2 is placed so
that it subtends a total angle of less than 0min to the centroid of BT, and lies directly to
the right of it. Let A = AT u A2 We also add n points to BT in a vertical row, in the same
relative position to A2 as the first vertical row of BT was to the left-hand group of A. Call
this new row B2 and let B = BT U B2. A and B are shown in Figure 13.
Now, any translation t for which BT ? I E A?T will also have B e t c A?. Fix such a I
and consider values of 0 where 101 ? 0min As 0 changes through this range, the points in B2
will sweep across the gaps in A2?. Their spacing is such that only one point will be crossing
a gap at a time. Thus, as we vary 0, the points of B2 achieve ?(n2) different configurations
with respect to the gaps of A2?. For this choice of I, there are thus ?(n2) values of 0 for
which dR(t, 0) < e, since any rotation in this range keeps re(B) ? I c A?. We can choose I to
represent one of the ?(n4) distinct configurations of B with respect to A, and so this gives
?(n6) different configurations of B with respect to the gaps of AE for which dR(I, 0) < ?.
These configurations are not connected in (I, 0) space, since any path from one to another
must cause at least one point to cross some gap.
15
6 Point sets under translation and scale
In this section, we consider the complexity of the graph of the llausdorff distance between two
sets of points as one set is translated and scaled with respect to the other. This scaling is with
respect to fixed x and y axes. This transformation group is of interest because it has been
used in image-recognition tasks, as described in [6]. It corresponds to the transformations
that the image of an object may undergo under the weak perspective projection model as a
camera is moved forward or panned about a vertical axis.
We will present three different lower-bound constructions: one each for the L1, L2 and
L? norms. They are all similar in concept, and are based on the constructions in Section 2,
using techniques from Section 4. All of these constructions show lower bounds for both the
directed and undirected llausdorff distance. The central idea here is that changing 8: slightly
has very little effect on points which are near the ? axis, while it has a largely translational
effect on groups of points which are located a large distance along the x axis ("large" here
means that the distance of the group from the origin is large relative to the size of the group).
6.1 The L2 example
This example is very similar to the example for point sets under rigid motion. Again, a key
observation is that the construction of AT and BT in Subsection 2.2 can be perturbed slightly
without affecting the topology of the graph. In this case, this perturbation will take the form
of a slight scaling of BT in x and y. Suppose that the origin is placed at the lower left corner
of BT. Then let 8min be the valid range of such scaling: if 1 --H 8min < 8:, 8? < 1 t 8min, then
there are ?(n?) translational configurations of RT with respect to AT for which replacing BT
by Ss?s? (BT) does not change the configuration (i.e. the same points are on the same sides
of the gap of AT?). 8min clearly depends on the n, ? and a used to construct AT and BT.
First, we construct A2 as in Section 4, and place it so that the ? axis cuts through the
left-hand scalloped edge in a manner similar to that described in Section 4: each lobe of the
scalloped edge contains a length 1 of the y axis, the smallest depth of any of the gaps is w,
and the ratio between the axis length contained in any lobe (i.e. 1) and the length contained
in the space next to that lobe is greater than 8n : 1. Note that this construction does not
depend on the location of this copy of A2 along the ? axis.
We next construct AT and BT as in 2.2 such that the region of ?(n3) complexity occupies
a region less than min(w/2, l/(8n)) square, and position them so that the lower left corner
of this region in translation space is located at t = (0, 0), and the lower left corner of BT is
at the origin. This determines a value for 8min We then position the copy of A2 a distance
of t/8min above the origin, with the y axis cutting through it as described above. We also
make a copy of A2, rotated by 900, to the right of the copy of AT, with the x axis cutting
through the lower scalloped edge in the same manner. A consists of AT together with these
two copies of A2. B then consists of BT plus two rows of n points plus an extra point per
row, as described in Subsection 4; one row and its extra point are positioned along the y
axis inside the uppermost lobe of the first copy of A2; the other row and its extra point are
in the corresponding position on the x axis, in the second copy of A2. Call these two rows
B2.
16
Now, it is possible to independently choose seven numbers ..,... ,n7 from 1 to n --H 1 and
construct a translation t and scale 3?, 8,, of B with respect to A where d8(t, Sx, 8y) < ? in
the following manner:
1.
n1, n2 and n3 determine the translation. They are used to position n1 of the points of
the lower row of BT to the left of the gap in AT?, n2 of the points of the upper row to
the left of the gap, and with the rows straddling the n3th "wobble" of the gap.
2. n4 and n5 determine s,,. They are used to position n4 of the points of the row of B2
lying on the y axis below one of the gaps in the scalloped edge of the upper copy of
A2. n5 selects the gap. Note that changing s,, acts as (essentially) a translation of this
row, as its distance from the origin (and therefore its y coordinate) greatly exceeds its
length. It is possible to do this no matter what translation was chosen above, since
the range of translations is small. Also, any 8,, chosen in this manner will not exceed
the range determined by 8min
3. n6 and n7 similarly determine Sx, by positioning the points of the row of B2 lying on
the x axis with respect to its copy of A2.
Now, if two such configurations are generated with different flj values, then it will not be
possible to move from one to the other without some point crossing a gap, and so they must
belong to different connected components in transformation space where d8(t, Sx, 8,,) < ?.
Also, due to the "extra points" added to the various parts of B, h(A, Ss:s?(B) ? t) is no
greater than ? for all such configurations; D8 therefore has ?(n7) distinct local minima.
These can occur in an arbitrarily small region of transformation space for a fixed e.
6.2 The L1 example
This example is quite similar to the example in the previous subsection. The construction
uses a copy of AT and BT from Subsection 2.1 (the translational example for L?), rotated
450 Instead of A2 being a row of points generating a scalloped edge, it is instead a row of
points generating a sawtooth edge; however, it is used in the same manner.
6.3 The L? example
This example must be constructed differently from the previous two, since a vertical row
of points, when dilated by ?, generates a straight vertical edge, with no irregularities that
can be exploited. In this case, however, we simply build A and B by taking three identical
copies of AT and BT from Subsection 2.1, placing one copy at the origin (copy 1), one far
out on the x axis (copy 2), and one far out on the y axis (copy 3). Now, we choose a
trauslational configuration of one of the copies of AT with respect to its copy of BT (the
copies are identical so which copy is used as a base is irrelevant), and initially set 8z and
8,, to 1. Now, adjusting 8z slightly moves only copy 2 of BT significantly, and moves it in a
largely translational manner in the direction of the x axis. As it moves, its points will cross
the gap in copy 2 of AT?. It can move both forward and backward, as 8? can be varied both
17
slightly above and slightly below 1. There are therefore ?(n2) configurations of copy 2 of BT
with respect to copy 2 of AT?, once the overall translational configuration has been chosen.
We similarly choose one of ?(n2) configurations for copy 3 of AT and BT, by adjusting s?.
The distance of copies 2 and 3 of AT and BT from the origin can be made as large as desired,
to reduce the non-trauslational effects of changing s? and si, until they are small enough
that they have no effect on the topology of the graph of Ds. This construction method also
works for the L1 and L2 norms.
7 Sets of points and line segments under translation
and scale
This example is quite similar to the previous example; we make a copy of AT and BT from
Section 3, shown in Figure 9, placed near the origin, together with a copy of the right-hand
group of each placed some distance away along the x axis, and a copy of the left-hand group
of each placed some distance away along the g axis. Similar observations give ?(n5) distinct
local minima for ds. Note that, as before, the exact norm being used is not relevant, since
it does not affect the gaps between the segments.
8 Point sets under affine transformation
Here we are dealing with transformations which map B to M(B) ? t, where M is a 2 x 2
matrix defined by
m00 m01
m10 m11
and t = (t?, t?) is a translation. In other words, each point (b?, b?) c B is mapped to
(moob: t m01b? t t?, miob: t miib? t t?).
The key observation here is that if B consists of three groups of points, one near the
origin, one located a large distance along the x axis, and one located a large distance along
the y axis, then
o+ Changing m00 slightly causes the second group in the transformed B to translate in x,
but has little other effect.
o+ Changing m10 slightly causes the second group to translate in y, but has little other
effect.
o+ Changing m01 or m11 slightly similarly causes the third group to translate in x or y,
and has little other effect.
o+ If A' is sufficiently close to the identity matrix, then M(B) will essentially be the same
as B, with the relative positions of the three groups shifted around somewhat.
Further, the magnitude of these translational motions with respect to their other effects
can be increased by moving the corresponding group farther away from the origin along the
18
appropriate axis. Thus, we have a six-parameter system (two transiational and four linear
parameters), which can be decomposed into three two-parameter transiationa] systems, plus
a small amount of "slop", which can be made as small as required. In order to build a
example, we simply take three copies of the appropriate AT and BT, and arrange them as
described above. Again, we can move copies 2 and 3 of AT and BT out from the origin until
all non-translational effects are not significant, since as they move farther out, the amounts
by which the mi> values need to be adjusted are reduced. Since all the copies of AT and BT
have ?(n3) complexity under translation, for both the directed and undirected llausdorff
distance, and are essentially independent, this construction gives ?(n9) complexity for both
dA and DA.
9 Sets of points and line segments under affine trans-
formation
This example is constructed identically to the previous example. We simply take three copies
of AT and BT from Section 3 and position them as before. This gives ?(n12) local minima
of dA, from three essentially independent ?(n4) translational examples.
10 Summary
We have presented constructions which give lower bounds on the complexity of the directed
and undirected Hausdorff distance in several different contexts. Several of the constructions
have shown that the directed llausdorff distance can have large complexity in small space,
and this observation has led to lower bounds on the undirected Hausdorff distance.
The problems for which lower bounds on the complexity of the undirected Hausdorff
distance were not shown were those involving sets of points and line segments. A remain-
ing open problem is that of determining such bounds. For example, is it possible for the
undirected llausdorff distance under translation between such sets to have large complexity
in a small space? If not, can this distance have any complexity greater than ?(n3)? Also,
is it possible to develop algorithms such as those in [4] which find the minimum llausdorff
distance under the action of some transformation group in less time than that given by the
complexity of the graph of the Hausdorff distance function?
11 Acknowledgments
The author would like to thank Paul Chew and Klara Kedem for the ?(n4) example shown
in Section 3.
19
References
[1]
P.K. Agarwal, M. Sharir, and 5. Toledo. Applications of parametric searching in geomet-
ric optimization. In Proc. Third ACM-SIAM Symposium on Discrete Algorithms, pages
72--H82,1992.
[2] H. Alt, B. Behrends, and J. Blomer. Approximate matching of polygonal shapes. In
Proc. Seventh ACM Symposium on Computational Geometry, 1991.
[3]
[4]
[5]
L.P. Chew, M.T. Goodrich, D.P. Huttenlocher, K. Kedem, J.M. Kleinberg, and
D. Kravets. Geometric pattern matching under Euclidean motion. In Proc. Fifth Cana-
dian Conference on Computational Geometry, pages 151--H156, Waterloo, Ontario, August
1993.
L.P. Chew and K. Kedem. Improvements on approximate pattern matching problems.
In 0. Nurmi and E. Ukkonen, editors, Proc. Third Scandinavian Workshop on Algorithm
Theory. Lecture Notes in Computer Science 621, Springer-Verlag, 1992.
D.P. Huttenlocher, K. Kedem, and M. Sharir. The upper envelope of Voronoi surfaces
and its applications. In Proceedings of Seventh A CM Symposium on Computational
Geometry, pages 194--H203, 1991. To appear in Discrete Computational Geometry.
[6] D.P. Huttenlocher and W.J. Rucklidge. A multi-resolution technique for comparing im-
ages using the Hausdorff distance. In Proc. Computer Vision and Pattern Recognition,
pages 705--H706, New York, NY, 1993.
[7] G. Rote. Computing the minimum llausdorff distance between two point sets on a line
under translation. Infonnation Processing Letters, 38(3):123--H127, May 1991.
20
