### Abstract

Given a set of points S = {v1, . . . , vn} ⊂ R^{m}, and a set of positive numbers r_{i}, i = 1, . . . , n, we wish to determine if there exists p ∈ Conv(S) such that d(p, v_{i}) = r_{i} 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 al- gorithm that in O(mnε^{-2} ln ε^{-1}) arithmetic operations computes pε ∈ Conv(S) such that one of the three con- ditions hold; (1): d(p_{ε}, v_{i})-r_{i} < ε, for all i = 1, . . . , n; (2): d(p_{ε}, v_{i}) < ri, for all i = 1, . . . , n; (3): d(p_{ε}, v_{i}) > ri, for all i = 1, . . . , n. In case of (2), no point p with pre- scribed 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.

Original language | English (US) |
---|---|

Pages | 271-276 |

Number of pages | 6 |

State | Published - Dec 1 2012 |

Event | 24th Canadian Conference on Computational Geometry, CCCG 2012 - Charlottetown, PE, Canada Duration: Aug 8 2012 → Aug 10 2012 |

### Other

Other | 24th Canadian Conference on Computational Geometry, CCCG 2012 |
---|---|

Country | Canada |

City | Charlottetown, PE |

Period | 8/8/12 → 8/10/12 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Computational Mathematics
- Geometry and Topology

### Cite this

*Finding a lost treasure in convex hull of points from known distances*. 271-276. Paper presented at 24th Canadian Conference on Computational Geometry, CCCG 2012, Charlottetown, PE, Canada.

}

**Finding a lost treasure in convex hull of points from known distances.** / Kalantari, Bahman.

Research output: Contribution to conference › Paper

TY - CONF

T1 - Finding a lost treasure in convex hull of points from known distances

AU - Kalantari, Bahman

PY - 2012/12/1

Y1 - 2012/12/1

N2 - Given a set of points S = {v1, . . . , vn} ⊂ Rm, 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 al- gorithm that in O(mnε-2 ln ε-1) arithmetic operations computes pε ∈ Conv(S) such that one of the three con- ditions hold; (1): d(pε, vi)-ri < ε, for all i = 1, . . . , n; (2): d(pε, vi) < ri, for all i = 1, . . . , n; (3): d(pε, vi) > ri, for all i = 1, . . . , n. In case of (2), no point p with pre- scribed 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.

AB - Given a set of points S = {v1, . . . , vn} ⊂ Rm, 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 al- gorithm that in O(mnε-2 ln ε-1) arithmetic operations computes pε ∈ Conv(S) such that one of the three con- ditions hold; (1): d(pε, vi)-ri < ε, for all i = 1, . . . , n; (2): d(pε, vi) < ri, for all i = 1, . . . , n; (3): d(pε, vi) > ri, for all i = 1, . . . , n. In case of (2), no point p with pre- scribed 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.

UR - http://www.scopus.com/inward/record.url?scp=84883017321&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883017321&partnerID=8YFLogxK

M3 - Paper

SP - 271

EP - 276

ER -