Problem Detail: 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?
Asked By : cagirici
Answered By : Craig Gidney
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/28507 3.2K people like this
