Triangulation Algorithm Based on Empty Convex Set Condition

Abstract

The article is devoted to generalization of Delaunay triangulation. We suggest to consider empty condition for special convex sets. For given finite set P ⊂ Rn we shall say that empty condition for convex set B ⊂ Rn is fullfiled if P ∩ B = P ∩ ∂B. Let Φ = Φα, α ∈ A be a family of compact convex sets with non empty inner. Consider some nondegenerate simplex S ⊂ Rn with vertexes p0,...,pn. We define the girth set B(S) ∈ Φ if qi ∈ ∂B(S), i = 0, 1, ..., n. We suppose that the family Φ has the property: for arbitrary nondegenerate simplex S there is only one the girth set B(S). We prove the following main result. Theorem 1. If the family Φ = Φα, α ∈ A of convex sets have the pointed above property then for the girth sets it is true: 1. The set B(S) is uniquely determined by any simplex with vertexes on ∂B(S). 2. Let S1, S2 be two nondegenerate simplexes such that B(S1) ≠ B(S2). If the intersection B(S1) ∩ B(S2) is not empty, then the intersection of boundaries B(S1), B(S2) is (n − 2)-dimensional convex surface, lying in some hyperplane. 3. If two simplexes S1 and S2 don’t intersect by inner points and have common (n − 1)-dimensional face G and A, B are vertexes don’t belong to face G and vertex B of simplex B(S2) such that B ∉ B(S1) then B(S2) does not contain the vertex A of simplex S1. These statements allow us to define Φ-triangulation correctly by the following way. The given triangulation T of finite set P ⊂ Rn is called Φ-triangulation if for all simlex S ∈ T the girth set B(S) ∈ Φ is empty. In the paper we give algorithm for construct Φ-triangulation arbitrary finite set P ⊂ Rn. Besides we describe examples of families Φ for which we prove the existence and uniqueness of girth set B(S) for arbitrary nondegenerate simplex S.

Keywords

• triangulation
• empty shpere condition
• Delaunay triangulation
• convex set
• convex function
• convex hull