sci.math.research (moderated) #8791 (7 + 109 more) [1]+-[1]
From: "Alexandre Gonalves" |-[1]--[1]
Newsgroups: sci.math,sci.math.research,comp.graphics.algorithms |-[1]
[1] Is the Hausdorff distance a metric ? \-[1]--[1]
Date: Tue Sep 16 05:59:23 EDT 1997
Hi to all
The Hausdorff distance is defined as
dH(A,B) = max [for x in A] of min [for y in B] of some_distance(x, y)
Taking the "some_distance" as the 2-D Euclidean distance, and for the
special case where A, B and C are 2-D polylines (lines with a finite
number of vertices), does this function verify the property:
dH (A, C) <= dH (A, B) + dH(B, C) ??
Thanks Alexandre (alexg@civil.ist.utl.pt)
End of article 8791 (of 8822) -- what next? [npq]
sci.math.research (moderated) #8800 (6 + 109 more) (1)+-[1]
From: mcmcclur@bulldog.unca.edu (Mark C McClure) |-[1]--[1]
Date: Tue Sep 16 10:01:24 EDT 1997
Yes, the Hausdorff distance is a metric on the set of all non-empty,
compact subsets of Euclidean space. Most books on fractal geometry prove
this. See, for example, Edgar, "Measure, Topology, and Fractal Geometry".
Mark McClure
Department of Mathematics
University of North Carolina at Asheville
http://www.unca.edu/~mcmcclur/
End of article 8800 (of 8822) -- what next? [npq]
sci.math.research (moderated) #8796 (5 + 109 more) (1)+-(1)
From: israel@math.ubc.ca (Robert Israel) |-[1]--[1]
Date: Tue Sep 16 13:16:42 EDT 1997
|> dH(A,B) = max [for x in A] of min [for y in B] of some_distance(x, y)
No it isn't. Among other problems, that wouldn't be symmetric in A and B,
i.e. you wouldn't have dH(A,B) = dH(B,A). Instead it can be defined as
dH(A,B) = sup { dist(a,B), dist(b,A) : a in A, b in B }
where dist(a,B) = inf { d(a,b) : b in B }, and d is a metric.
The Hausdorff distance (defined the way I did it above) on nonempty subsets
of any metric space is always a metric. To show it, you just have
to show that
dist(a,C) <= dH(A,B) + dH(B,C) and dist(c,A) <= dH(A,B) + dH(B,C)
for all a in A and c in C.
Consider the first inequality. For any epsilon > 0, there is b in B so
d(a,b) <= dist(a,B) + epsilon. Since dist(a,B) <= dH(A,B), for every
c in C we have
d(a,c) <= d(a,b) + d(b,c) <= dH(A,B) + epsilon + d(b,c)
which implies
dist(a,C) <= dH(A,B) + epsilon + dist(b,C) <= dH(A,B) + epsilon + dH(B,C)
Take epsilon -> 0 to get dist(a,C) <= dH(A,B) + dH(B,C).
Interchanging A and C, and using the symmetry of dH, we get
dist(c,A) <= dH(A,B) + dH(B,C) as well.
Robert Israel israel@math.ubc.ca
Department of Mathematics (604) 822-3629
University of British Columbia fax 822-6074
Vancouver, BC, Canada V6T 1Y4
End of article 8796 (of 8822) -- what next? [npq]
sci.math.research (moderated) #8805 (4 + 109 more) (1)+-(1)
From: israel@math.ubc.ca (Robert Israel) |-(1)--[1]
Date: Thu Sep 18 01:38:40 EDT 1997
I should have said it's a pseudometric, or assumed the sets are closed.
Otherwise, it's possible to have dH(A,B) = 0 in cases where A and B are
different (but have the same closure).
End of article 8805 (of 8822) -- what next? [npq]
sci.math.research (moderated) #8793 (3 + 109 more) (1)+-(1)
From: scott@math.csuohio.edu (Brian M. Scott) |-(1)--(1)
Date: Tue Sep 16 13:46:45 EDT 1997
> dH(A,B) = max [for x in A] of min [for y in B] of some_distance(x, y)
This isn't quite right: it makes dH asymmetric. Given a metric d on
the underlying space, define d(x, A) = inf [for y in A] of d(x, y).
Then
dH(A,B) = max{sup [for x in A] of d(x,B), sup [for x in B] of d(x,A)}.
>Taking the "some_distance" as the 2-D Euclidean distance, and for the
>special case where A, B and C are 2-D polylines (lines with a finite
>number of vertices), does this function verify the property:
> dH (A, C) <= dH (A, B) + dH(B, C) ??
Given r > 0, define V(A,r) to be the union of open r-balls centred at
points of A. Show first that dH(A,B) < r if and only if A is
contained in V(B,r) and B is contained in V(A,r). Now assume that
dH(A,B) < r and dH(B,C) < s, and let x in A. Then since x in V(B,r),
there is a y in B such that d(x,y) < r. Similarly, there is z in C
such that d(y,z) < s. Therefore d(x,C) < r + s, so A is contained in
V(C, r+s). Similarly, C is contained in V(A, r+s), so dH(A,C) < r+s.
The result follows.
Brian M. Scott
End of article 8793 (of 8822) -- what next? [npq]
sci.math.research (moderated) #8795 (2 + 109 more) (1)+-(1)
From: John Rickard |-(1)--(1)
Date: Tue Sep 16 13:53:12 EDT 1997
: dH (A, C) <= dH (A, B) + dH(B, C) ??
Are you sure you have the right definition? Yes, the function
satisfies that property (since every point in A is distant at most
dH(A,B) from a point in B, and every point in B is distant at most
dH(B,C) from a point in C, so every point in A is distant at most
dH(A,B)+dH(B,C) from a point in C). However, it is not a metric,
since it does not satisfy
dH(A,B) = dH(B,A).
--
John Rickard
End of article 8795 (of 8822) -- what next? [npq]
sci.math.research (moderated) #8798 (1 + 109 more) (1)+-(1)
From: kovarik@mcmail.CIS.McMaster.CA (Zdislav V. Kovarik) |-(1)--(1)
Date: Tue Sep 16 22:03:08 EDT 1997
First of all, it is not clear whether dH(A,B) = dH(B,A) for all (non-empty
closed) subsets A,B of a bounded space M, or for all non-empty bounded
subsets A,B of an arbitrary metric space. I think we can construct counterexamples.
A remedy (consult Dieudonne, Foundations of Modern Analysis, 3.16,
Exercise 3) is: define (imposing symmetry by brute force)
dsH(A,B) = max(dH(A,B), dH(B,A))
This dsH will be a metric if the underlying metric space is bounded, or if
we restrict ourselves to bounded closed sets.
Cheers, ZVK (Slavek).
End of article 8798 (of 8822) -- what next? [npq]
sci.math.research (moderated) #8799 (0 + 109 more) (1)+-(1)
From: David Epstein |-(1)--(1)
[1] Re: Is the Hausdorff distance a metric ? |-(1)
Date: Wed Sep 17 12:06:33 EDT 1997 |-(1)
Let A = [-s,0], B = [0,1], C = [1,1+s]
Then d(A,C) = 1+s, d(A,B) = s and d(B,C) = s.
If we take s small, the triangle inequality is not satisfied.
But maybe I've misunderstood the question.
David Epstein
End of article 8799 (of 8822) -- what next? [npq]