### 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 |

### All Science Journal Classification (ASJC) codes

- Computational Mathematics
- Geometry and Topology

## Fingerprint Dive into the research topics of 'Finding a lost treasure in convex hull of points from known distances'. Together they form a unique fingerprint.

## 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.