5
$\begingroup$

An algorithm I've implemented to tessellate an N-dimensional space requires starting with a bounding N-simplex.

Given a set of $k$ points $S_{0..k-1} \subset R^N$ is there a procedure to find a simplex $P$ with vertices $V_{0..N+1}$ which would contain $S$?

A test of $S_j$ being interior to the simplex and not on or outside of the manifold of $(N-1)$-simplex facets would be:

  • For each $i$ in $0..N+1$
    • Create a new copy of $V$ called $V'$
    • Replace $V'_i$ with $S_j$
    • if $det(V'_1-V'_0, V'_2-V'_0, ..., V'_{N-1}-V'_0, V'_{N}-V'_0) < 0$ then test fails because the new test simplex has a negative oriented volume (assume the vector differences are represented as columnar vectors in an NxN matrix, and we are taking the determinant to find the oriented volume of the associated parallelotope.)
  • End For

Ideas I haven't tried yet, but that may work:

  • Create a bounding hypersphere, then inscribe the hypersphere onto the facets of a new simplex which would contain the entire hypersphere, ergo it would also contain $S$.
  • Create a bounding axis-aligned orthotope, then somehow find a simplex that contains the orthotope
$\endgroup$
5
  • $\begingroup$ Your hypersphere idea seems good; should be quite efficient to implement. You don't need to inscribe it exactly, it would be enough to take a simplex known to contain the hypersphere. If you're not interested in a tight fit, that approach seems nice and simple. $\endgroup$
    – joriki
    Apr 28, 2011 at 19:07
  • $\begingroup$ Thanks @joriki, I found a nice paper on doing the opposite thing here: geometrictools.com/Documentation/CentersOfSimplex.pdf but as of yet I'm unsure how to actually go about the construction of a simplex from a hypersphere. $\endgroup$
    – Will Bradley
    Apr 28, 2011 at 19:41
  • $\begingroup$ Similar to your orthope idea, you can choose an origin so that all the points lie in the positive orthant. Then project the points onto $v=(1,1,\dots,1)$. Find a plane $P$ that is perpendicular to $v$, and farther from the origin than all the point projections. An enclosing simplex is given by the origin and the points where $P$ intersects the axes. $\endgroup$
    – yasmar
    Apr 28, 2011 at 19:49
  • $\begingroup$ @yasmar, that's a great idea. It makes sense. I believe it's possible to do without normalizing the points, as well. In order to maintain counter-clockwise winding of the vertices (or "orientation"), I'm guessing I'll have to order the vertices based on dimensionality of the solutions. So, the first vertex is the minimum in all dimensions, the second vertex is the solution along the x-unit ray emanating from that point. The second vertex is the solution along the y-unit ray emanating from that point,etc...? $\endgroup$
    – Will Bradley
    Apr 28, 2011 at 20:04
  • $\begingroup$ Yes, if you project onto the line generated by $v$, there should be no need to normalize the points. If you have an oriented coordinate axis, you can use that to get the orientation on the standard simplex which corresponds to the $N-1$-face that lies in the hyperplane $P$. That should be a way to start with the orientation problem. $\endgroup$
    – yasmar
    Apr 28, 2011 at 20:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .