Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading the logic paper "Interpolation in fuzzy logic" by Matthias Baaz and Helmut Veith http://www.springerlink.com/content/654wl9u5mcj7qtva/

On page 479 it is claimed that "It suffices to show that continuous piecewise linear functions are closed under taking suprema and infima of a single coordinate $y$; geometrically, this means taking the upper boundary of the union of orthogonal projections of all polytopes on the hyperplane y = 0, [15]."

Unfortunately, reference [15] is non helpful at all because it is said that [15] is "Hryniv, O.: Personal Communication."

Thus, I am wondering how to prove that if $f: [0,1]^{n+1} \longmapsto [0,1]$ is a continuous piecewise linear function then the function $\bigwedge f: [0,1]^n \longmapsto [0,1]$ defined by $$ (\bigwedge f) (\vec{x}):= \inf \{ f(y,\vec{x}): y \in [0,1] \} $$ is also a continuous piecewise linear function. Can anybody suggest a way to prove this statement?

Indeed, I am more interested in a similar statement: if $f$ is a continuous piecewise linear function with rational coefficients then $\bigwedge f$ is also continuous piecewise linear with rational coefficients. I suspect that a proof of the previous result can give me hints about how to prove this statement.

share|improve this question
1  
Are there finitely many "pieces" (nodes?) underlying the continuous piecewise linear functions? –  hardmath Jun 30 '11 at 12:22
    
Yes, there are finitely many pieces (and each one of them can be thought as the convex hull of a finite set of points) –  boumol Jun 30 '11 at 13:47

1 Answer 1

up vote 3 down vote accepted

I'll denote elements of $[0,1]^{n+1}$ by $\vec z$ and elements of $[0,1]^{n}$ by $\vec x$.

First, $\bigwedge f$ is continuous. For each linear piece $f_i$, there is $\lambda_i$ such that $|f_i(\vec z)-f_i(\vec z_0)|<\lambda_i|\vec z-\vec z_0|$. Then by dividing the segment between $\vec{z}$ and $\vec{z_0}$ into parts according to the linear pieces, we can conclude that $|f(\vec z)-f(\vec z_0)|<\lambda|\vec z-\vec z_0|$ with $\lambda=\max \lambda_i$.

For $\vec x,\vec x_0\in[0,1]^n$, let $\hat y$ and $\hat y_0$ be the respective values of $y$ and $y_0$ at which the infima of $f(y,\vec x)$ and $f(y_0,\vec x_0)$ are attained. If $f(\hat y,\vec x)\ge f(\hat y_0,\vec x_0)$, then

$$ \begin{eqnarray} \left|(\bigwedge f) (\vec{x})- (\bigwedge f) (\vec{x}_0)\right| &=& f(\hat y,\vec x)-f(\hat y_0,\vec x_0) \\ &=& (f(\hat y,\vec x)-f(\hat y_0,\vec x))+(f(\hat y_0,\vec x)-f(\hat y_0,\vec x_0)) \\ &\le& f(\hat y_0,\vec x)-f(\hat y_0,\vec x_0) \\ &\le& \lambda\left|\vec x-\vec x_0\right|\;, \end{eqnarray} $$

and likewise, if $f(\hat y,\vec x)\le f(\hat y_0,\vec x_0)$, then

$$ \begin{eqnarray} \left|(\bigwedge f) (\vec{x})- (\bigwedge f) (\vec{x}_0)\right| &=& f(\hat y_0,\vec x_0)-f(\hat y,\vec x) \\ &=& (f(\hat y_0,\vec x_0)-f(\hat y,\vec x_0))+(f(\hat y,\vec x_0)-f(\hat y,\vec x)) \\ &\le& f(\hat y,\vec x_0)-f(\hat y,\vec x) \\ &\le& \lambda\left|\vec x-\vec x_0\right|\;. \end{eqnarray} $$

Thus $\bigwedge f$ is continuous. To see that it is piecewise linear, orthogonally project all the points defining the pieces of $f$ to $[0,1]^n$ and triangulate the resulting set of points. For each piece $f_i$ of $f$, let $D_i$ be the orthogonal projection of the domain of $f_i$ to $[0,1]^n$. Then for each simplex of the triangulation and each piece $f_i$, the simplex is either entirely inside or entirely outside $D_i$, and the infimum $\bigwedge f_i$ of $f_i$ with respect to $y$ is a linear function on the simplex (since it is attained at the boundary of the domain of $f_i$, that boundary is a linear function of $\vec x$ within the simplex, and $f_i$ is linear). Thus, on each simplex, $\bigwedge f$ is the infimum with respect to $i$ of the infima $\bigwedge f_i$ of all pieces $f_i$ for which $D_i$ contains the simplex. For each pair of these $\bigwedge f_i$, find the hyperplane on which they are equal and, if the hyperplane intersects the simplex, subdivide the simplex accordingly. Then on each resulting polytope, $\bigwedge f$ is defined by one of the $\bigwedge f_i$ alone, which is a linear function on the simplex, and therefore on the polytope. Thus $\bigwedge f$ is piecewise linear.

share|improve this answer
    
Thanks for the answer. Which "triangulation result" are you using here? –  boumol Jul 1 '11 at 7:55
    
@boumol: You're welcome. I'm not sure what part you're asking about; the expression "triangulation result" doesn't occur in the answer. As far as I'm aware, I was just using the fact that any point set can be triangulated; see e.g. en.wikipedia.org/wiki/Triangulation_(geometry) and en.wikipedia.org/wiki/Point_set_triangulation. –  joriki Jul 1 '11 at 8:15
    
OK I see. Thus, the natural generalization to the rational setting (see the last part of my question) is whether it is true or false that every finite set of rational points can be "rationally triangulated". Any suggestion for a book where I can find similar statements (and a proof of the triangulation theorem)? –  boumol Jul 1 '11 at 14:20
1  
@boumol: I don't know what you mean by "rationally triangulated". If the pieces of $f$ have rational coefficients and the points defining them have rational coordinates, then an argument analogous to the one I gave shows that the same will be true for $\bigwedge f$, since substituting a rational linear boundary into a rational linear function again yields a rational linear function. –  joriki Jul 3 '11 at 12:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.