| This work deals with the problem of asymptotically-optimal simplicial approximation of vector fields over Euclidean domains of any dimension.;We begin by describing the difference between the piecewise-constant vector field approximation problem, and the problem of approximation of gradient fields of scalar functions. In particular, we show that the latter definition of the problem is sensitive to the alignment of edges with principal directions, a fact whose importance had been underestimated for these kinds of problems. This observation leads to some negative results: we show that the transformational method cannot produce asymptotically-optimal approximations when used to approximate gradient fields, and is only asymptotically-optimal for vector field approximation of everywhere-convex inputs.;In order to construct proper simplicial complexes without element inversions, we introduce several results regarding the well-behavedeness of Voronoi diagrams with respect to non-Euclidean metrics, and their dual simplicial complexes. In studying these Voronoi diagrams, it will become clear that a certain notion of variation of the metric can be used to characterize how small the Voronoi regions must be to ensure that they are connected. These diagrams are then dualized into simplicial complexes. Of particular interest is a generalization of Delaunay triangulations to non-Euclidean metrics that satisfies an empty circumscribing ellipsoid property, similar to the empty circumcircle property of Delaunay triangulations. This property always holds for duals of certain well-behaved Voronoi diagrams, and guarantees that they are proper simplicial complexes (no overlapping or inverted elements), much like the empty circumcircle property does for Delaunay triangulations. This result is of particular interest because it describes a generalization of Delaunay triangulations to non-Euclidean metrics that preserves some of it's most important desirable properties.;The rest of this document describes a construction for asymptotically-optimal piecewise-constant approximation of generic vector fields. This construction uses the previously-mentioned tools to ensure well-behavedeness of the constructed simplicial complexes. In the limit, it produces no more than 4 n+1 times more vertices than the most efficient approximation, where n is the dimension, and it works in the presence of singularities. Finally, a characterization of the size of the output is provided. |
