On the Complexity of Trilateration With Noisy Range Measurements
Recent developments, especially in wireless and mobile networks, have enabled the use of location based services in many application areas. Accurate location discovery, however, is still an open problem. A widely used and practical localization method is trilateration. However, trilateration works best when exact range measurements are available, which is not apparently the case in real-world due to device errors or environmental noise. In this paper, localization through trilateration when the distance measurements are imprecise, is shown to be NP-complete. Moreover, the authors also prove that no matter how small the ranging errors get, the problem is still intractable.