every pair of points of the form |xi xj ( jit is clear that if we are given the set of pointsit is easy to construct the set of distances in ( time this set will not be sortedbut if we are willing to settle for an ( log ntime boundthe distances can be sortedtoo the turnpike reconstruction problem is to reconstruct point set from the distances this finds applications in physics and molecular biology (see the references for pointers to more specific informationthe name derives from the analogy of points to turnpike exits on east coast highways just as factoring seems harder than multiplicationthe reconstruction problem seems harder than the construction problem nobody has been able to give an algorithm that is guaranteed to work in polynomial time the algorithm that we will present generally runs in ( log nbut can take exponential time in the worst case of coursegiven one solution to the probleman infinite number of others can be constructed by adding an offset to all the points this is why we insist that the first point is anchored at and that the point set that constitutes solution is output in nondecreasing order let be the set of distancesand assume that |dm ( )/ as an examplesuppose that { since | we know that we start the algorithm by setting clearlyx since is the largest element in we remove from the points that we have placed and the remaining distances are as shown in the following figurex { the largest remaining distance is which means that either or by symmetrywe can conclude that the choice is unimportantsince either both choices lead to solutions (which are mirror images of each other)or neither doso we can set without affecting the solution we then remove the distances and from dobtaining { the next step is not obvious since is the largest value in deither or if then the distances and must also be present in quick check shows that indeed they are on the other handif we set then - and must be present in these distances are also in dso we have no guidance on which choice to make thuswe try one and see if it leads to solution if it turns out that it does notwe can come back and try the other trying the first choicewe set which leaves {