Klyachin V.A. Triangulation Algorithm Based on Empty Convex Set Condition
- Details
- Hits: 1109
http://dx.doi.org/10.15688/jvolsu1.2015.3.3
Klyachin Vladimir Aleksandrovich
Doctor of Physical and Mathematical Sciences,
Head of Department of Computer Science and Experimental Mathematics,
Volgograd State University
This email address is being protected from spambots. You need JavaScript enabled to view it. , This email address is being protected from spambots. You need JavaScript enabled to view it.
Head of Department of Computer Science and Experimental Mathematics,
Volgograd State University
This email address is being protected from spambots. You need JavaScript enabled to view it. , This email address is being protected from spambots. You need JavaScript enabled to view it.
Prosp. Universitetsky, 100, 400062 Volgograd, Russian Federation
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.
Key words: triangulation, empty shpere condition, Delaunay triangulation, convex set, convex function, convex hull.
Triangulation Algorithm Based on Empty Convex Set Condition by Klyachin V.A. is licensed under a Creative Commons Attribution 4.0 International License.
Citation in English: Science Journal of Volgograd State University. Mathematics. Physics. №3 (28) 2015 pp. 27-33
 3_klyachin.pdfURL: https://mp.jvolsu.com/index.php/en/component/attachments/download/440 | 1651 Downloads |