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]