[julia-users] Re: Hausdorff distance

2015-10-26 Thread Andrew McLean 
The naïve algorithm is O(N^2), I think the most efficient algorithms come 
close to O(N). There is quite a lot of literature on efficient algorithms.

- Andrew

On Friday, 23 October 2015 23:28:46 UTC+1, Júlio Hoffimann wrote:

> Hi,
>
> I want to make the Hausdorff distance (
> https://en.wikipedia.org/wiki/Hausdorff_distance) available in Julia, is 
> the Distances.jl package a good fit or I should create a separate package 
> just for this distance between point sets?
>
> I can think of a very simple (naive) implementation:
>
> using Distances
>
> A, B # matrices which columns represent the points in the pointset
> D = pairwise(Euclidean(), A, B)
> daB = maximum(minimum(D,2))
> dbA = maximum(minimum(D,1))
> result = max(daB, dbA)
>
> -Júlio
>

Re: [julia-users] Re: Hausdorff distance

2015-10-26 Thread Júlio Hoffimann 
Hi Andrew,

Could you please point to a good paper? This naive implementation I showed
is working surprisingly well for me though.

-Júlio

Re: [julia-users] Re: Hausdorff distance

2015-10-26 Thread Andrew McLean 
This is not exactly my area of expertise, but this recently published paper
looks like a good starting point.

[1]
A. A. Taha and A. Hanbury, ‘An Efficient Algorithm for Calculating the
Exact Hausdorff Distance’, *IEEE Transactions on Pattern Analysis and
Machine Intelligence*, vol. 37, no. 11, pp. 2153–2163, Nov. 2015.

http://dx.doi.org/10.1109/TPAMI.2015.2408351


On 26 October 2015 at 14:22, Júlio Hoffimann 
wrote:

> Hi Andrew,
>
> Could you please point to a good paper? This naive implementation I showed
> is working surprisingly well for me though.
>
> -Júlio
>

Re: [julia-users] Re: Hausdorff distance

2015-10-26 Thread Júlio Hoffimann 
Thanks, will take a look.

-Júlio