Finding a Lost Treasure in Convex Hull of Points From Known Distances
Bahman Kalantari · Canadian Conference on Computational Geometry · 2012
Given a set of points S = {v1, . . . , vn} ⊂ R, and a set of positive numbers ri, i = 1, . . . , n, we wish to determine if there exists p ∈ Conv(S) such that d(p, vi) = ri for all i = 1, . . . , n, where d(·, ·) denotes the Euclidean distance. We refer to this as the ambiguous convex hull problem. Given ǫ > 0, we describe an algorithm that in O(mnǫ ln ǫ) arithmetic operations computes pǫ ∈ Conv(S) such that one of the three conditions hold; (1): |d(pǫ, vi)− ri| ri, for all i = 1, . . . , n. In case of (2), no point p with prescribed distances belongs to Conv(S). In case of (3), no point p with prescribed distances exists. In case of (1), we give an estimate on d(pǫ, p). The algorithm is a variation of the Triangle Algorithm in [8] for the convex hull decision problem where p is given explicitly.