I was having a look at this question and then reading about Tarjan's least common ancestors algorithm. I never came across any applications of LCA algorithms before.
Where are such LCA algorithms commonly used?
views:
68answers:
2
+2
A:
Don't know where it is used, but I have a couple ideas where it might get used:
computer graphics: often 3D sceneries get split into cubes which form a tree structure. If you have an object which is contained in two such cubes a LCA algorithm gives you the smallest containing larger cube.
analysis of gens in order to find the relationships between species and their lowest common ancestor
merge algorithms of version control systems
Jens Schauder
2010-08-22 17:34:02
thanks! version control -> three way merge: http://en.wikipedia.org/wiki/Merge_(revision_control)#Three-way_merge
Lazer
2010-08-22 17:39:56
It is also useful for certain kinds of string processing when looking for root words for different suffixes.
Arnold Spence
2010-08-22 18:13:52
+1
A:
In compilers, the LCA of two basic blocks is a place you can put a computation so it is available to both. This might be useful for eliminating common subexpressions, or inserting phi-node for SSA conversion. These algorithms are well evolved and highly optimized, though, so the LCA itself may be hard to see, e.g., SSA and PRE
Doug Currie
2010-08-22 17:37:54