how to do it with less walking in the worst case?

Walk the square root of 2 (approx 1.4) kilometers starting from the tree in each of 4 directions where each direction is 90 degrees from the previous direction (i.e. north, south, east, west). This should cause you to cross any straight trail coming within a mile of your current position and worst case would be walking approx 5.7 miles before finding the trail. I think?

-Mike