Triangulation algorithm based on empty convex set condition

The article is devoted to generalization of Delaunay triangulation. We suggest to consider empty condition for special convex sets. For given finite set ⊂ R𝑛 we shall say that empty condition for convex set ⊂ R𝑛 is fullfiled if ∩𝐵 = ∩𝜕𝐵. Let Φ = Φ𝛼, ∈ be a family of compact convex sets with non empty inner. Consider some nondegenerate simplex ⊂ R𝑛 with vertexes 𝑝0,..., 𝑝𝑛. We define the girth set 𝐵(𝑆) ∈ Φ if ∈ 𝜕𝐵(𝑆), = 0, 1,..., 𝑛. We suppose that the family Φ has the property: for arbitrary nondegenerate simplex there is only one the girth set 𝐵(𝑆). We prove the following main result. Theorem 1. If the family Φ = Φ𝛼, ∈ of convex sets have the pointed above property then for the girth sets it is true: 1. The set 𝐵(𝑆) is uniquely determined by any simplex with vertexes on 𝜕𝐵(𝑆). 2. Let 𝑆1, 𝑆2 be two nondegenerate simplexes such that 𝐵(𝑆1) ̸= 𝐵(𝑆2). If the intersection 𝐵(𝑆1) ∩ 𝐵(𝑆2) is not empty, then the intersection of boundaries 𝐵(𝑆1),𝐵(𝑆2) is (𝑛 - 2)-dimensional convex surface, lying in some hyperplane. 3. If two simplexes 𝑆1 and 𝑆2 don’t intersect by inner points and have common (𝑛 - 1)-dimensional face and 𝐴, are vertexes don’t belong to face and vertex of simplex 𝐵(𝑆2) such that 𝐵 ̸∈ 𝐵(𝑆1) then 𝐵(𝑆2) does not contain the vertex of simplex 𝑆1. These statements allow us to define Φ-triangulation correctly by the following way. The given triangulation of finite set ⊂ R𝑛 is called Φ-triangulation if for all simlex ∈ the girth set 𝐵(𝑆) ∈ 𝑃ℎ𝑖 is empty. In the paper we give algorithm for construct Φ-triangulation arbitrary finite set ⊂ R𝑛. Besides we describe exapmles of families Φ for which we prove the existence and uniqueness of girth set 𝐵(𝑆) for arbitrary nondegenerate simplex 𝑆.