Thin discrete triangular meshes

Abstract

In this paper we present an approach to describe polyhedra by meshes of discrete triangles. The study is based on the theory of arithmetic discrete geometry (J.-P. Reveilles, Geometrie discrete, calcul en nombres entiers ct algorithmique, These d'etat, Universite Louis Pasteur, Strasbourg, December 1991). As distinct from the previous investigations on this topic, the triangles we introduce are parts of the thinnest possible discrete 6-tunnel-free planes, i.e., those that are usually used in practice. Given a plane P in the space, we define a 6-tunnel-free discrete plane, called a regular plane, which appears to be the best approximation to P. Given a mesh of triangles, we propose a method to approximate any triangle by a discrete triangular patch - a portion of a regular plane, and we prove that the resulting triangular mesh is 6-tunnel-free. The properties of the approximation obtained make the suggested approach convenient for practical applications. (C) 2000 Elsevier Science B.V. All rights reserved.