ENCRYPTION OF 3D PLANE IN GIS USING VORONOI-DELAUNAY TRIANGULATIONS AND CATALAN NUMBERS

Abstract

A method of encryption of the 3D plane in Geographic Information Systems (GIS) is presented. The method is derived using Voronoi-Delaunay triangulation and properties of Catalan numbers. The Voronoi-Delaunay incremental algorithm is presented as one of the most commonly used triangulation techniques for random point selection. In accordance with the multiple applications of Catalan numbers in solving combinatorial problems and their "bit-balanced" characteristic, the process of encrypting and decrypting the coordinates of points using the Lattice Path method (walk on the integer lattice) or LIFO model is given. The triangulation of the plane started using decimal coordinates of a set of given planar points. Afterward, the resulting decimal values of the coordinates are converted to corresponding binary records and the encryption process starts by a random selection of the Catalan key according to the LIFO model. These binary coordinates are again converted into their original decimal values, which enables the process of encrypted triangulation. The original triangulation of the plane can be generated by restarting the triangulation algorithm. Due to its exceptional efficiency in terms of launching programs on various computer architectures and operating systems, Java programming language enables an efficient implementation of our method.