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 $P\subset \mathbb{R}^n$ we shall say that empty condition for convex set $B\subset \mathbb{R}^n$ is fullfiled if $P\cap B=P\cap \partial B$. Let $\Phi=\Phi_{\alpha}, \alpha \in {\mathcal A}$ be a family of compact convex sets with non empty inner. Consider some nondegenerate simplex $S\subset \mathbb{R}^n$ with vertexes $p_0,...,p_n$. We define the girth set $B(S)\in \Phi$ if $q_i\in \partial B(S), i=0,1,...,n$. We suppose that the family $\Phi$ 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 $\Phi=\Phi_{\alpha}, \alpha\in {\mathcal A}$ of convex sets have the pointed above property then for the girth sets it is true:

• The set $B(S)$ is uniquely determined by any simplex with vertexes on $\partial B(S)$.
• Let $S_1,S_2$ be two nondegenerate simplexes such that $B(S_1)\ne B(S_2)$. If the intersection $B(S_1)\cap B(S_2)$ is not empty, then the intersection of boundaries $B(S_1), B(S_2)$ is $(n-2)$-dimensional convex surface, lying in some hyperplane.
• If two simplexes $S_1$ and $S_2$ 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(S_2)$ such that $B\not \in B(S_1)$ then $B(S_2)$ does not contain the vertex $A$ of simplex $S_1$.

These statements allow us to define $\Phi$-triangulation correctly by the following way. The given triangulation $T$ of finite set $P\subset \mathbb{R}^n$ is called $\Phi$-triangulation if for all simlex $S\in T$ the girth set $B(S)\in Phi$ is empty. In the paper we give algorithm for construct $\Phi$-triangulation arbitrary finite set $P\subset \mathbb{R}^n$. Besides we describe exapmles of families $\Phi$ for which we prove the existence and uniqueness of girth set $B(S)$ for arbitrary nondegenerate simplex $S$.