An Upper Bound on Trilaterating Simple Polygons.
Matthew Dippel, Ravi Sundaram · Canadian Conference on Computational Geometry · 2015
In this work, we introduce the Minimum Trilateration Problem, the problem of placing distance measuring guards in a polygon in order to locate points in the interior. We provide the first non-trivial bounds on trilaterating simple polygons, by showing that b 8N 9 c guards suffice for any non-degenerate polygon of N sides, and present an O(N logN) algorithm for the corresponding placement. We also show how this mapping can be efficiently inverted, in order to determine a point’s location given its distances to the guards which can see it.