What’s the name of this class of geometric satisfiability problems?

Posted on by

I asked a little while ago on Twitter about whether there’s a given (searchable) name for a class of problem, and I realize given the answers that there isn’t enough information in 140 characters.

So here’s an attempt to state the problem more clearly:

Suppose you are told there are N points in \Re^{m}, but not their positions, and are also given a list of Euclidean distances between some (or all) pairs of those points. You are asked to determine whether the distances are feasible or not.

For example, suppose I say there are four points in a plane, A, B, C and D, and that the distance ||AB|| = 1, ||BC|| = 1, ||CD|| = 2 and ||AD|| = 3; if I’ve done the sketching right, those distances are feasible for points in a plane. If however ||AD|| = 9, the distances are infeasible.

Another way to frame an example, I guess, is to simply ask is it possible that there are four points in \Re^{4}, A, B, C and D, and that the distance ||AB|| = 1, ||AC|| = 1, ||BC|| = 1, ||CD|| = 1 and ||AD|| = 2?

What I’m wondering is whether this class of geometric constraint satisfaction problems has a particular name that one might, you know, look up. Like the Boolean satisfiability problem and the knapsack problem have special names all their own.

5 thoughts on “What’s the name of this class of geometric satisfiability problems?”

  3. This makes *much* more sense than it did on Twitter :-) . Assuming you’re in a “standard” Euclidean space, you’re essentially asking if the given distances satisfy the triangle inequality. You can generalize this to other metrics & spaces, which takes you into measure theory as mentioned above.

    As far as a class name, something like TriangleInequalityChecker? (I’m crap at names, I’m afraid.)

  4. Thanks Nic. The triangle inequality thing should be a lead, as well. Ed’s metric space links also seem to be leading me to the correct mathematicians’ terms.

    You and Ron Jeffries think alike. I never really meant “what should I name the class in a program?”; I meant class as in “type” or “category”!

  5. It looks promising that questions of this type might generally be answered by restricting your google search to ams.org, e.g.

    site:ams.org Euclidean distances between pairs

    as a search string corresponding to the URL

    http://www.google.com/search?client=safari&rls=en&q=site:ams.org+Euclidean+distances+between+pairs&ie=UTF-8&oe=UTF-8

    has a page of stuff which includes some AMS feature articles which look like surveys worth noting.

Leave a Reply