Klyachin V.A., Popov V.V. Chains method for storage of multidimensional triangulation

Details

Hits: 1479

Klyachin Vladimir Alеksandrovich

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.
Prospect Universitetsky, 100, 400062 Volgograd, Russian Federation

Popov Vladimir Valеntinovich

Candidate of Physical and Mathematical Sciences, Associate Professor, 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.
Prospect Universitetsky, 100, 400062 Volgograd, Russian Federation

Abstract. This study is an attempt to obtain lower bounds for the amount of memory required to store the data of multi-dimensional triangulations. The author offers a method of organizing storage triangulation, allowing in n+1 times to reduce the amount of memory in comparison with one of the standard methods. The essence of the method proposed by the author is the partitioning of the set of simplices in an array of chains adjacent simplices. Neighborhood relations can be written in a more compact structure of the triangulation. More accurately. If μ(f) denotes the number of bits occupied by storage triangulation N points in Rⁿ by one of the standard ways, then , where  m — number of simplexes. Whereas the proposed method of storage triangulation this limit is 1 for any dimension. To investigate the optimal method, the author formalises the problem and introduces the concept of triangulation as a way to store one-to-one mapping of the set of all triangulations of a set of points in Rⁿ on the set of natural numbers N. Thus, the method of storage — a comparison of each triangulation identify the unique natural number. Study the accuracy of the asymptotic estimates leads to the problem of obtaining lower triangulations given set of points. This article discusses two examples where such a calculation is accurate. In both cases,there is the exponential growth for number of triangulations depended on the number of points. Reference to recent works by foreign mathematicians say about general behavior of the number of such triangulations in the plane. This allows the author to hypothesize the existence of such a storage method of triangulation, in which the memory capacity increases linearly with the number of points. In particular, we expect that the optimal value of the above limit is 0.

Key words: triangulation, simplex, memory volume estimate, number of triangulations, Catalan number.

Chains method for storage of multidimensional triangulation by Klyachin V.A., Popov V.V. is licensed under a Creative Commons Attribution 4.0 International License.

Citation in English: Science Journal of Volgograd State University. Mathematics. Physics. №2 (19) 2013 pp. 71-79

Attachments:

V. A. Klyachin, V. V. Popov URL: https://mp.jvolsu.com/index.php/en/component/attachments/download/156

806 Downloads