A question: I inferred this from your demo, but wanted to confirm with you: The index returned by a query is guaranteed to correspond to the row index of the data used to create the kd-tree, correct?

I hope you don't mind my posting this modified version; if you like it, feel free to use it to update your package or do whatever you see fit.

function [dFrechet, coupling] = fcn_discreteFrechetDistance(P, Q, dist_fcn)

% P and Q: two curves represented by matrices of size dim by number
% dist_fcn: optional distance function handle; default to Eucleandian

[n1, p] = size(P);
[n2, q] = size(Q);

if (n1 ~= n2)
error('P and Q mismatch');
end

switch nargin
case 2
dist_fcn = @(x, y) sqrt(sum((x - y).^2));
case 3
otherwise
error('wrong number of arguments');
end

% This is worked on by the inner function
CA = -ones(p, q);

% This is also worked on by the inner functions.
% Each cell stores four numbers [[u_last; v_last], [u_new; v_new]].
% The first column is an index into the cell array, and the second column
% is the newly added edge
coupling_cell = cell(p, q);

I'm not quite sure about your question, but let me try to answer anyway:

The "ending point" recursion for the chain should parallel the value recursion which stores the results in CA (without repeating the work already done). In this case you would need a second variable to store where the "last time" ending point was. I am saying "this time" and "last time" because the recursion goes backwards. For example, in the (i > 1 && j > 1) case, the ending point is (i,j), but depending on which of the 3 cases has the min value, the "last time" could be (i-1, j-1), (i-1, j) or (i, j-1).

1. You can add a second return value that gives the coupling sequence. More on this below.

2. You can move the distance function handle into the call list, as an optional third argument. This makes it more versatile without incurring extra cost.

3. To get the coupling sequence, you can add a cell array at the level of CA (by the way, persistence is not needed), with each cell recording two things: an index into the cell array that gives where the coupling sequence ends "last time," and the new coupling pair that is added "this time."

4. You can change the c() function to do two things: modifying CA, and modifying the cell array, during the if-then-else branches. Return value is not needed.

5. After a call to c(p, q), you can get the distance from CA(p, q), and trace backwards the coupling sequence starting from the cell array at (p, q).