Shortest distance

Point me in the right direction with this problem since I have no idea on how to tackle it.You're given 4 set of coordinates in R^3 that form a tetrahedron, then another 4 set of coordinates in R^3 that form another tetrahedron.
How do I find the smallest distance from the surface of one tetrahedron to the other?

1. Calculate distance between centers of tetrahedrons. Call it R
2. Convert everything to voxels
3. From each point of surface run A* search in all directions
4. If A* encounters voxel of another tetrahedron, congratulations!
5. From all found distances choose the smallest
6. If it is slow, buy better servers and reimplement everything in erlang to run this hardest taks across the worldglobe.