Triangulation algorithm based on empty convex set condition

V. A. Klyachin

Matematičeskaâ fizika i kompʹûternoe modelirovanie, no. 3 (2015), pp. 27-33.

Résumé

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$.

Détail

Mots-clés : triangulation, Delaunay triangulation
Keywords: empty shpere condition, convex set, convex function, convex hull.

Bibliographie

[1] B.\;N. Delaunay, “On the Empty Sphere. To the Memory of Georges Voronoi”, per. s fr. A.\;Yu. Igumnov, Zapiski seminara «Sverkhmedlennye protsessy», 1, 2006, 147–153

[2] V.\;A. Klyachin, “On Some Generalization of Delaunay Condition”, Vestn. Tomsk. gos. un-ta. Matem. i mekh., 2008, no. 1 (2), 48–50 | MR

[3] V.\;A. Klyachin, V.\;V. Popov, “Chain Method for Storage of Multidimensional Triangulations”, Science Journal of Volgograd State University. Mathematics. Physics, 2013, no. 2 (19), 71–79 | DOI

[4] A.\;A. Mayorov, T.\;K. Nguen, “Effective Algorithm of Delaunay Triangulation”, Izvestiya vysshikh uchebnykh zavedeniy. Geodeziya i aerofotosyemka, 2011, no. 1, 105–108

[5] A.\;V. Skvortsov, N.\;S. Mirza, Analisys and Algorithms of Triangulations, Izd-vo Tomsk. un-ta Publ., Tomsk, 2006, 168 pp.

[6] B.\;N. Delaunay, “Sur la sphère vide. A la mémoire de Georges Voronoï”, Izvestiya: Mathematics, 1934, no. 6, 793–800