[Lemon-user] Min weighted complete graph matching

[Pierre Alliez]

dear all,

I am a novice in graph matching but I have started using  the munkres 
algortihm to solve the min weighted complete graph matching for a 
problem which involves two sets of 3D points (say, A and B, of same 
cardinality).

My problem is related to optimal transport where the input points are 
seen as unitary masses and the transport plan is restricted to be binary 
(I must transport one entire point of A to one entire point of B). My 
goal is to find the optimal transport plan from A to B, i.e., the plan 
which minimizes the sum of distances or square distances, etc.

I noticed that the algorithm requires a dense matrix, which does not 
really scale to large point sets. Is there any way to provide a sparse 
matrix to the algorithm?

Another question not related to Lemon but to the algorithm itself: are 
there special instances of the Min weighted complete graph matching 
problem when we have a complete knowledge of the embedding of the 
points? (and maybe more, such as a Voronoi diagram of both point sets, 
the mutual locations of points in the Voronoi cells of other set, etc). 
I attach two images that depict the set A and the set B - I am hoping 
that a variant can better scale.

Also, are there hierarchical versions of the problem? I could cluster 
the points in A recursively, etc.

any advice/pointers would be greatly appreciated,

best regards,

-- 
Pierre Alliez
GEOMETRICA
INRIA Sophia Antipolis - Mediterranee
http://www-sop.inria.fr/members/Pierre.Alliez/
Tel: +33 492 387 677

-------------- next part --------------
A non-text attachment was scrubbed...
Name: cvd1.png
Type: image/png
Size: 19722 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20121128/df5c3d22/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cvd2.png
Type: image/png
Size: 20894 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20121128/df5c3d22/attachment-0001.png>