Surface Approximation and Geometric Partitions (Q4210082)

Given a surface that is schlicht over the \((x,y)\)-plane, the authors are inspired by the study of the complexity of the problem of finding a simplicial surface of minimal complexity that gives a Chebyshev approximation of the given surface for a given precision \(\varepsilon\). They show that the problem of finding an approximation of a set of points on such a surface by triangles whose orthogonal projections into the \((x,y)\)-plane are mutually disjoint is NP-hard, and conclude that the given problem probably also is NP-hard. The main results depend on a notion of recursively separable partition of a collection of convex sets. The collection is recursively if either it contains only one set or there is a line not intersecting any of the sets and such that each halfplane of that line contains some sets of the collection and the collection in each halfplane is recursively separable. It is shown that if a set of \(n\) points in the plane can be covered by \(k\) trapezoids parallel to the \(x\)-axis and compatible with a Boolean subset condition then there is a recursively separable covering by this kind of trapezoid of size \(O(k\log k)\). They also show that there exists a polynomial time algorithm that for two finite disjoint sets in the plane yields covers by trapezoids (or triangles) so that no covering set contains points of different kinds. These results are then applied to Chebyshev approximations of simple sets in three spaces.