Computational Geometry Method for DTOA Triangulation

摘要

We present a computational geometry method for the problem of triangulation in the plane using measurements of distance-differences. Compared to existing solutions to this well-studied problem, this method is: (a) computationally more efficient and adaptive in that its precision can be controlled as a function of the number of computational operations, making it suitable to low power devices, and (b) robust with respect to measurement and computational errors, and is not susceptible to numerical instabilities typical of existing linear algebraic or quadratic methods. This method employs a binary search on a distance-difference curve in the plane using a second distance difference as the objective function. We establish the unimodality of the directional derivative of the objective function within each of a small number of suitably decomposed regions of the plane to support the binary search. The computational complexity of this method is O(log2 1/gamma), where the computed solution is guaranteed to be within a gamma-precision region centered at the actual solution. We present simulation results to compare this method with existing DTOA triangulation methods.