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

Research output: Contribution to conferencePaper

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages271-276
Number of pages6
StatePublished - Dec 1 2012
Event24th Canadian Conference on Computational Geometry, CCCG 2012 - Charlottetown, PE, Canada
Duration: Aug 8 2012Aug 10 2012

Other

Other24th Canadian Conference on Computational Geometry, CCCG 2012
CountryCanada
CityCharlottetown, PE
Period8/8/128/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

    Kalantari, B. (2012). 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.