2
$\begingroup$

I have a function $f$ defined on the positive integer lattice in $\mathbb{R}^n$ (i.e. the vectors in $\mathbb{R}^n$ whose coordinates are all nonnegative integers). I want to extend the domain of $f$ to all of $\mathbb{R}^n_{\ge 0}$ in such a way that $f$ is continuous. I think the best way to do this is by coming up with some simplicization of the integer lattice, then expressing each point by its barycentric coordinates in its simplex and using this to compute a weighted average of the value of the function at the vertices of the simplex.

What is a good, simple way to simplicize the integer lattice, so that when I take a point on input I can quickly determine which $n+1$ lattice points define the simplex containing my point?

$\endgroup$
2
  • $\begingroup$ is your question really about simplicizing (whatever that should mean) the integers lattice, or about extending your function? $\endgroup$ Commented Apr 20, 2013 at 0:28
  • $\begingroup$ It's about simplicizing, as stated. That particular method of extending my function has some other desirable properties, which I won't get into. Simplicizing is the higher-dimensional analogue of triangulation. For example, a good way to simplicize the integer lattice in $\mathbb{R}^2$ is to split each square into two right triangles, one with hypotenuse facing northeast, one with hypotenuse facing southwest. $\endgroup$ Commented Apr 20, 2013 at 0:32

2 Answers 2

Reset to default
1
$\begingroup$

there are many ways to obtain a simplicial subdivision of $R^n$ that will include the integer lattice points. Without further knowledge of the properties of the extension you seek it is very hard to give a good answer (notice that just to obtain a continuous extension (or even infinitely differentiable one) of a function defined on a set of isolated points can be done quit trivially).

Any way, for a simplicial subdivision, you can just consider each hypercube of adjacent lattice vertices, add the point in the middle, and connect it to all the vertices in the hypercube. Then consider each face of the hypercube and connect all the dots there. Then connects all the dots in any face of a face, and so on.

$\endgroup$
0
$\begingroup$

A good way to do the simpex division can be based on the ordering of the coordinates. In the unit hypercube with coordinates $(x_1,...,x_n)$ with each $x_i \in \{ 0,1 \}$, define a simplex for each ordering of the list of coordinates to be that sequence obtained by only using the vertices of the hypercube which are in that ordering. Then on taking a given input point, you only need check the ordering of (fractional parts of) its coordinates to see which of these simplices to use, and what are the vertices for that simplex. Note that there are (as expected) $n!$ such simplices making up each $n$-cube.

Of course this must be done "modulo the integer lattice", that is, one must first take integer and fractional parts of the given point $P$ in $n$-space, and then get its simplex (using the ordering of its fractional parts) in the unit hypercube whose origin is at the point given by the floors of the coordinates of $P$.

For example in the 3-space unit cube with the ordering $x_2 \le x_3 \le x_1$ our four vertices will be $$[1]\ \ (0,0,0),\ (1,0,0),\ (1,0,1),\ (1,1,1),$$ these being all the $0,1$ triples whose coordinates satisfy $x_2 \le x_3 \le x_1$.

This means for example that the data point $(4.7,9.2,16.4)$ would be associated to the hypercube based at $(4,9,16),$ and then since the fractional parts satisfy $.2 <.4<.7$ we are in the case $x_2 \le x_3 \le x_1$ mentioned above and use the simplex with vertices mentioned in [1].

$\endgroup$
2
  • $\begingroup$ This is perfect - the ability to quickly extract the vertices of the simplex from a sample point is exactly what I was looking for. Thank you. $\endgroup$ Commented Apr 21, 2013 at 21:12
  • 1
    $\begingroup$ I fooled around with the automatic determination of the scalars to multiply the vertices of the simplex by, to get the weights by which to multiply given lattice values by, in order to get the value of the "simplex linear" extension to random points $P$ not on the lattice. I think the expressions are pretty simply related to the ranked fractional parts of coordinates of $P$, but didn't include details of that. $\endgroup$ Commented Apr 21, 2013 at 22:06

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.