6
$\begingroup$

Consider an undirected weighted graph $G = (V,E)$, where $V \subset \mathbb{R}^3$ so the points are 3D, and the weight of an edge equals the (Euclidean) distance between its endpoints. Note that we're not given the coordinates of the points in V. We may not even be given all pairwise distances, so the graph need not be complete, and it may even be sparse.

Suppose we're given $k$ and told that there are $k$ planes such that all the vertices belong to at least one of those plane. We want to find $k$ such planes, with an added restriction:

In order to determine whether 4 points are coplanar given only their pairwise distances, the most straightforward method is to use the Cayley-Menger determinant. For our problem, this would require the graph to be fairly dense, since we'd need to know most of the pairwise distances to apply Cayley-Menger. The restriction is to find $k$ planes without using the Cayley-Menger determinant.

If this is impossible, can we obtain a proof that states this is impossible? In other words, can we prove that for any such graph $G$ and given $k$, if we have enough information to find $k$ planes for $G$ by some means, then we have enough information to use Cayley-Menger to find $k$ planes?

Improve this question
$\endgroup$
11
  • $\begingroup$ a ref that the Cayley-Menger determinant is sufficient for that purpose would be helpful if you know one. what do you mean "all pairwise distances between each 4 nodes"? isnt there as many pairwise distances as edges with pts taken as vertices on a graph? is the algorithm you have in mind looking at coplanarity of all 4-point choices? more on coplanar $\endgroup$ Commented Jul 22, 2014 at 3:10
  • $\begingroup$ idea: think this generalizes. put all the points in a matrix and find its rank. if its 2, they are all coplanar. this might go over better on Mathematics...? $\endgroup$ Commented Jul 22, 2014 at 4:37
  • $\begingroup$ @vzn That is a fine idea but what if there are more than one coplanar sensor groups? $\endgroup$ Commented Jul 22, 2014 at 8:03
  • $\begingroup$ It's not clear what you're asking. Do we get the points or not? What do you mean exactly by "given set of points and pairwise distances (not the coordinates)"? Give an example. $\endgroup$ Commented Jul 22, 2014 at 14:18
  • 1
    $\begingroup$ In general, the $k$ planes might not be unique. For instance if the vertices are vertices of a cube, and $k = 2$, then the top and bottom plane work, as do the front and back, as do the left and right. You were talking about the $k$ planes, but presumably you're okay with finding any $k$ planes that still do the trick of covering all points in $V$? $\endgroup$ Commented Jul 22, 2014 at 16:04

4 Answers 4

Reset to default
3
+25
$\begingroup$

I think that if the input graph is 3-connected, and you assume some arbitrary origin and orientation, you can recreate the original points. Especially if you can find K_4 to seed the triangulation process.

Once we have the points, greedy strategies become available. They might not be optimal, but maybe they're enough for your purposes.

I've asked about recovering the embedding as a separate question.

Random Greedy

Until we have fewer than three not-disqualified points, arbitrarily pick three of them, yield the plane going through them, and mark all points on the plane as disqualified.

Take the remaining not-disqualified points (if any), pair them with some arbitrary disqualified points, and yield the plane going through them.

The planes we yielded covered all of the points. The number of planes we yielded is at most $\frac{n}{3}$, and each requires scanning through the remaining points, so this algorithm takes $O(n^2)$ time (faster than computing a determinant).

If the number of planes $k \ll n$, then we have reasonably good odds of hitting one of the large planes. I'm not sure what the expected running time is, but I would wild-guess it at $O(n \, k^3 \log k)$. (That's based on the coupon collector problem implying we need $\approx k \log k$ hits to collect $k$ planes, and that the odds of a hit are $\approx (1/k)^2$ so the expected time between hits is $\approx k^2$).

Prioritized Greedy

Another thing we can do, if we can solve for the points, is iterate over all triplets and count how many points are on that plane. Then we repeatedly yield the plane covering the most points, until no points are left.

If we don't account for disqualified points when choosing the next plane, then this takes $O(n^3 \log t)$ time where $t$ is the number of planes we return. If we do re-prioritize, then I think it can still be done in $O(n^3 \log t)$ (the number of disqualified points on other planes can only change by 2 so it might be possible to rebalance in some clever way).

This approach should do better, but again I don't think it's guaranteed to have $t=k$. We can probably arrange the points so that taking the plane covering most of them sends us down the wrong path.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Your very first sentence of the first algorithm basically says "pick 3 points, and disqualify all the points which are coplanar with those 3." But how do you determine which points are coplanar? That's the whole point of this question. Assuming that you don't know the coordinates of the points, and only know some of their pairwise distances, how do you detect coplanarity? $\endgroup$ Commented Jul 22, 2014 at 15:37
  • $\begingroup$ @AmitKumar Any arbitrary triplet of points is co-planar, because they define a plane. A corner case is when they're degenerate (two of the points are the same, or the three points fall on a line), in which case they're still co-planar but many planes can cover them. $\endgroup$ Commented Jul 22, 2014 at 16:11
  • $\begingroup$ @AmitKumar Oh, I see that you meant how do you test if a point is on a plane. Basically, dot product the the plane's normal against the point's delta to a point on the plane. When the dot product is zero (or near zero if you're approximating), the point is on the plane. You do this for each not-disqualified point. $\endgroup$ Commented Jul 22, 2014 at 16:15
  • $\begingroup$ @AmitKumarGupta To be a bit more precise, the question is not about how to discover which points are on a plane. It's about how to pick a small set of planes covering the points, with the additional wrinkle that you only get some of the interpoint distances instead of the points themselves. $\endgroup$ Commented Jul 22, 2014 at 16:18
  • 1
    $\begingroup$ @AmitKumarGupta If you have a K_4 then put one of them at (0,0,0), another at (x,0,0), the next at (y,z,0), and then the last at (a,b,c) with c > 0. If you can't solve for a unique embedding, up to translation/rotation/mirroring, then I don't think there's a well defined solution. You'd get things like rigid groups of points connected by a lever that you can rotate around without violating the distance constraints, and I don't think the planes can survive that loss of information. $\endgroup$ Commented Jul 22, 2014 at 16:34
3
$\begingroup$

RANSAC would be one candidate method to find planes that cover a large fraction of the points.

Suppose that a large fraction of the points go through some plane $P$, say, $n/10$ of them. Here's how we can find it:

So let's pick 4 points at random from the $n$; call those points $q,r,s,t$. Suppose we know the distances between all such pairs (they form a 4-clique, $K_4$). Then we can use the Cayley-Menger determinant to see if they are co-planar. Suppose they are co-planar. Then we might try testing each other point $x$ and seeing whether we can tell whether it is co-planar with the plane formed by $q,r,s,t$. We might only be able to test this when the additional point $u$ forms a 4-clique together with some other points known to be on the plane. At the end, if we've found a significant number of points that are on the plane formed by $q,r,s,t$, we keep this plane. Keep doing this for, say, 1000 random choices of $q,r,s,t$.

How well will this work? Well, suppose we model the graph as a random graph where each possible edge appears with probability $p$ (so we expect $pn(n-1)/2$ edges on average). Then the probability that a randomly chosen set of 4 points form a 4-clique in the graph is $p^6$. Therefore, if we sample at least $10^4/p^6$ choices of $q,r,s,t$, we expect to find at least one where they reveal the plane $P$. Also, the probability that an additional point $u$ forms a 4-clique with at least three of $p,q,r$ is $p^3$, so when we do find four points $q,r,s,t$ on the plane $P$, we expect to find at least $p^3 n/10$ of the points on the plane $P$. (Actually, we'll probably find a lot more than that. Once we have those $p^3 n/10$ points, now the probability that an additional point $v$ forms a 4-clique with at least three of them is $1-(1-p^3)^{p^3 n/10} \approx 1-\exp\{-p^6 n/10\}$, which is significantly larger than $p^3$.) In other words, once we find points $q,r,s,t$ on the plane $P$, it is likely that we will keep this plane.

So as long as you sample enough 4-combinations of points, and as long as your graph is dense enough, this procedure is likely to detect all planes that cover a large fraction of points.

Improve this answer
$\endgroup$
3
  • $\begingroup$ However, we again have to use Cayley-Menger determinant for each extra point we test. $\endgroup$ Commented Jul 22, 2014 at 17:02
  • $\begingroup$ @cagirici, yes, we do. My answer is consistent with the problem statement, to the level of detail provided in the question. If there's some reason why it doesn't address your particular setting, you might want to consider editing your question to provide a more specific set of technical requirements. ("Don't use Cayley-Menger" is not a valid technical requirement. "Must work on graphs that are very sparse" is a requirement, if you can formulate what you mean by "very sparse". A requirement states what you want to achieve, not how.) $\endgroup$ Commented Jul 22, 2014 at 17:14
  • $\begingroup$ after a long period, I'm back to that problem again :) If I say "the algorithm should work with inconsistent distance measurements", is this a requirement? If so, does this algorithm work with erroneous range measurements? $\endgroup$ Commented Oct 22, 2014 at 12:05
3
$\begingroup$

Unfortunately, the answer is that this is an NP-Complete problem. Using only 4 planes of points, you can encode satisfiability problems into whether or not there is a point set that generates a sparse set of distances.

That means you can create problems where determining if a fifth plane is necessary or not requires solving 3-SAT problems. You can combine two such problems, where exactly one requires the fifth plane, to keep the number of planes constant and force the algorithm to solve 3-SAT problems even if it knows $k$ ahead of time.

So the problem has no worst case polynomial time solution, unless P = NP.

Improve this answer
$\endgroup$
-1
$\begingroup$

am attempting an answer even though the question may be somewhat unclearly stated. half of it says the points are given, the other half says that pairwise distances are given. am going to assume that point coordinates are given for this answer. there is a close connection between computing determinant and matrix rank. there is a generalization as follows. create the matrix of 3d vectors, they can be either column or row vectors. compute the rank. if it is 2, the points are coplanar. the pairwise distances can be computed from the coordinates and is not necessary to calculate/ determine matrix rank.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Could you please copy and paste the sentence which states that the coordinates of the points are given? The question says a point set is given. Not the coordinates. $\endgroup$ Commented Jul 22, 2014 at 14:55
  • $\begingroup$ am taking "point set = coordinates". you say points are not complete in comments, but not in the question. how do you define "point sets" without coordinates? maybe this needs vote to close if its inconsistent or unanswerable in current form without revision. am attempting to extract something answerable. the comments & question dont all line up. the answer determines if all points are coplanar. maybe you only want to know if subsets of all points are coplanar given some pairwise distances? $\endgroup$ Commented Jul 22, 2014 at 15:02

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.