Polynomial-time approximation algorithms for anchor-free TDoA localization

We consider the problem of anchor-free self-calibration of receiver locations using only the reception time of signals produced at unknown locations and time points. In our settings the receivers are synchronized, so the time differences of arrival (TDoA) of the signals arriving at the receivers can be calculated. Given the set of distinguishable time points for all receivers the task is to determine the positions of the receivers as well as the signal sources. We present the first polynomial-time approximation algorithms for the minimum problem in the plane, in which the number of receivers is four, respectively the number of signals is three. For this, we first consider the problem that the time points of m signals are jittered by at most some is an element of > 0. We provide an algorithm which tests whether n given receiver positions are valid for measurements from m unknown senders with a run-time of O(n(2)m), and we provide an algorithm with run-time O(nm log m) which tests the validity of m given sender positions for n unknown receiver positions. Using these tests, we can compute all possible receiver and signal source positions in time O((root 2/is an element of)(2n-3)n(2)m), respectively O((root 2/is an element of)(2m-3)nm log m). (C) 2014 Elsevier B.V. All rights reserved.