Sign in to follow this  

n-simplexes

This topic is 4558 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

My problem is as follows: I have a point p in n-space laying in the cube defined by the two corners v_min and v_max each being a vector in n_space. eg \forall i \in \{ 0 .. n } v_min_i < = p_i <= v_max_i. I then need a clever way to construct a simplex that consist of n+1 vertices that all are corners in the box. I will denote the vertices of the simplex from s_0 to s_n. The simplex must be constructed in such a way that p can be written as a linear combination of s_i eg \sum_i=0^n k_i * s_i where k_i >= 0 and \sum_i=0^n k_i = 1. A brute force solution would be to test all possible simplexes, but as the dimension grow the number of possible simplexes grows at least exponentially and the running time would be unacceptable large. Does anyone know a clever way to either select the vertices that must be in the simplex or filter away the vertices that cannot possibly be part of the simplex until the n+1 corners of the simplex are found I thought about using hyperplanes spanned by some of the corners in n dimensions and filtering away all points that are at the wrong side of the plane It just comes to my mind that the problem also can be considered as follows: Construct the convex hull made out of the n+1 corners of the box that also contains p Best Regards Niels [Edited by - Boldt on June 22, 2005 9:45:50 AM]

Share this post


Link to post
Share on other sites
I believe the following should work, illustrated for vertices with zeros and ones, but should not be a problem in general. In 2D, let P = (p0,p1) be the point in the rectangle. Let V = (v0,v1) represent the vertices of the rectangle. If p0 >= p1, keep vertices for which v0 >= v1 is true. These are (0,0), (1,0), and (1,1), and they form a simplex (triangle) containing P. If p0 <= p1, keep vertices for which v0 <= v1 is true . These are (0,0), (0,1), and (1,1), and they form a simplex containing P.

In 3D, let P = (p0,p1,p2). If p0 <= p1 <= p2, keep vertices for which v0 <= v1 <= v2 is true. These vertices are (0,0,0), (0,0,1), (0,1,1), and (1,1,1), and they form a simplex (tetrahedron) containing P.

I do not have a formal proof, but I think this works in any dimension. The algorithm is to sort the components of P, p[i0] <= p[i1] <= ... <= p[in], where (i0,i1,...,in) is a permutation of (0,1,...,n). The simplex is formed by those vertices V for which v[i0] <= v[i1] <= ... <= v[in]. The sorting is O(n*log(n)) and the test of vertices if O(n), so the full algorithm is O(n*log(n)).

Share this post


Link to post
Share on other sites

This topic is 4558 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this