Optimal triangulation of saddle surfaces (Q1702150): Difference between revisions

The authors consider a piecewise linear approximation \(\hat{f}(x,y)\) of a bivariate quadratic function \[ f(x,y) = ax^2 + bxy +cy^2+dx+ey+g. \] The approximation \(\hat{f}(x,y)\) is defined by a triangulation \(\mathcal{T}\) of the plane \(\mathbb{R}^2\), and the aim of the authors is to find for any given \(\varepsilon > 0\) an approximating function, as `simple' as possible, satisfying the inequality \(|f(x,y)-\hat{f}(x,y) | \leq \varepsilon\) for all \((x,y) \in \mathbb{R}^2\). Here, the smallest possible value of \(\varepsilon\) satisfying this property is called the \textsl{vertical error} of the approximation. The `simplicity' of the approximating function is measured by the \textsl{triangle density} of the approximation, defined by the authors in the following way. Let \(Q_r\) denote the square \([-r/2,r/2]^2\). Then the triangle density of \(\hat{f}\) is the number of triangles in \(\mathcal{T}\) intersecting \(Q_r\) divided by the area of \(Q_r\), as \(r\) tends to infinity; or more precisely, it is defined as \[ \limsup_{r \to \infty} \frac{\left| \left\{ T \in \mathcal{T} : T \cap Q_r \neq \emptyset \right\} \right|}{r^2}. \] In their two main theorems the authors prove that if \(f\) is indefinite (i.e. \(ac-b^2 < 0\)), then there is a piecewise linear approximation \(\hat{f}\) of \(f\) with vertical error \(\varepsilon > 0\) that has triangle density \[ \frac{\sqrt{3}}{4} \cdot \frac{\sqrt{b^2-ac}}{\varepsilon} \approx 0.43301 \cdot \frac{\sqrt{b^2-ac}}{\varepsilon}. \] Furthermore, there is an interpolating piecewise linear approximation \(\hat{f}\) of \(f\) with vertical error \(\varepsilon > 0\) that has triangle density \[ \frac{2}{\sqrt{27}} \frac{\sqrt{b^2-ac}}{\varepsilon} \approx 0.44721 \cdot \frac{\sqrt{b^2-ac}}{\varepsilon}, \] and this bound is the best possible. Here, \(\hat{f}\) is called \textsl{interpolating} if \(\hat{f}\) satisfies the condition \(\hat{f}(x,y) = f(x,y)\) for all vertices \((x,y)\) of \(\mathcal{T}\). The authors note that the second result is due to \textit{H. Pottmann} et al. [J. Geom. Graph. 4, No. 1, 31--53 (2000; Zbl 0961.65011)], apart from stating the explicit bound.