Surface Approximation and Geometric Partitions
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.
- Computing large planar regions in terrains, with an application to fracture surfaces
- Algorithmic aspects of proportional symbol maps
- Approximating points by a piecewise linear function
- Delineating boundaries for imprecise regions
- Approximate range searching using binary space partitions
- The complexity of separating points in the plane
- Isotopic approximation within a tolerance volume
- Cup products on polyhedral approximations of 3D digital images
- Computing cup products in \(\mathbb{Z}_2\)-cohomology of 3D polyhedral complexes
- Computing optimal islands
- scientific article; zbMATH DE number 1003231 (Why is no real title available?)
- Approximating the k-Level in Three-Dimensional Plane Arrangements
- Splittings of Surfaces
- Computing Large Planar Regions in Terrains
- Online class cover problem
- Structured discrete shape approximation: theoretical complexity and practical algorithm
- Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets
This page was built for publication: Surface Approximation and Geometric Partitions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210082)