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
  • 0
    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](http://en.wikipedia.org/wiki/Simplex#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.2011-04-28

0 Answers 0