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

Research output: Contribution to conferencePaper

2 Citations (Scopus)

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

Fingerprint

Convex Hull
Ambiguous
Euclidean Distance
Decision problem
Set of points
Triangle
Denote
Estimate

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Geometry and Topology

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.
Kalantari, Bahman. / Finding a lost treasure in convex hull of points from known distances. Paper presented at 24th Canadian Conference on Computational Geometry, CCCG 2012, Charlottetown, PE, Canada.6 p.
@conference{42d1115486454e9595b93d71ea0541f7,
title = "Finding a lost treasure in convex hull of points from known distances",
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.",
author = "Bahman Kalantari",
year = "2012",
month = "12",
day = "1",
language = "English (US)",
pages = "271--276",
note = "24th Canadian Conference on Computational Geometry, CCCG 2012 ; Conference date: 08-08-2012 Through 10-08-2012",

}

Kalantari, B 2012, 'Finding a lost treasure in convex hull of points from known distances' Paper presented at 24th Canadian Conference on Computational Geometry, CCCG 2012, Charlottetown, PE, Canada, 8/8/12 - 8/10/12, pp. 271-276.

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

2012. 271-276 Paper presented at 24th Canadian Conference on Computational Geometry, CCCG 2012, Charlottetown, PE, Canada.

Research output: Contribution to conferencePaper

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 -

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