Optimizing Sensor Placements for Fixed Source Localization: A Distinct Subset Distance Sum Problem

This research addresses the problem of optimizing sensor placements for fixed source localization using distinct subset distance sums. Given a line L in R2 and a set P of n points on one side of L, we seek to locate a minimal set S of points on L such that for any two distinct subsets Q and R of P, there exists a point s∈S where the sum of reciprocal distances from Q to s uniquely identifies Q. Our results show that a minimal sensor set S of size 1 is always feasible, but computing this set exactly proves to be inefficient with an exponential worst-case complexity. To address this, we propose the use of approximation algorithms that reduce the time complexity while maintaining accuracy. Additionally, we explore the implementation of a threshold T, which ensures that the reciprocal distance sums of distinct subsets remain sufficiently separated. We also analyze how this threshold affects the size of S. Future work will focus on applying approximation techniques such as Well Separated Pairs Decomposition (WSPD) and coresets to achieve more efficient solutions, as well as further analyzing the impact of threshold implementation on sensor placement.