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

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?”

Bill -

This is not the answer, but it does have some set of the same words that you are looking for, and chasing references to and fro might work:

http://www.jstor.org/pss/2699760

and it looks like the answer might be somewhere in this piece of math

http://www.ams.org/mathscinet/msc/msc2010.html?t=&s=28A12&btn=Search&ls=s

Reply ↓

This looks promising as well, at least for defining some terms:

http://en.wikipedia.org/wiki/Measure_(mathematics)

Reply ↓

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

Reply ↓

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”!

Reply ↓

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.

Reply ↓

Notional Slurry

Pontification without all the gritty gravitas

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

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

Leave a Reply Cancel reply