I asked a lit­tle while ago on Twit­ter about whether there’s a given (search­able) name for a class of prob­lem, and I real­ize given the answers that there isn’t enough infor­ma­tion in 140 characters.

So here’s an attempt to state the prob­lem more clearly:

Sup­pose you are told there are points in , but not their posi­tions, and are also given a list of Euclid­ean dis­tances between some (or all) pairs of those points. You are asked to deter­mine whether the dis­tances are fea­si­ble or not.

For exam­ple, sup­pose I say there are four points in a plane, , , and , and that the dis­tance , , and ; if I’ve done the sketch­ing right, those dis­tances are fea­si­ble for points in a plane. If how­ever , the dis­tances are infea­si­ble.

Another way to frame an exam­ple, I guess, is to sim­ply ask is it pos­si­ble that there are four points in , , , and , and that the dis­tance , , , and ?

What I’m won­der­ing is whether this class of geo­met­ric con­straint sat­is­fac­tion prob­lems has a par­tic­u­lar name that one might, you know, look up. Like the Boolean sat­is­fi­a­bil­ity prob­lem and the knap­sack prob­lem have spe­cial names all their own.