Tyumen State University Herald. Physical and Mathematical Modeling. Oil, Gas, Energy


Releases Archive. Вестник ТюмГУ. Физико-математические науки. Информатика (№7, 2014)

Computation algorithm of convexo-concave contour of the seismic survey

About the authors:

Alexey Yu. Shcherbich, Development Manager, Data Management Sector, Halliburton Company (Russian Federation, Tyumen)
Vladimir N. Kutrunov, Dr. Sci. (Phys.-Math.), Professor, Department of Algebra and Mathematical Logics, University of Tyumen


Quality control methodology development is one of the key problems required by E&P industry due to the sufficiently increasing volumes of data. These methods are to increase both technological and commercial data value in terms of topical G&G data management issues. The article describes author’s algorithm for calculation of concave hulls applied to 2D and 3D seismic surveys. Computation algorithm is based on hypothesis that concave hull can be built on the basis of convex hull by including additional edges. This hypothesis is declared as a theorem and its proof is given in the article as well. Using additional strict criteria of points interrelations on a plane as preliminary defined lines sections, authors succeeded in solution of concave hull creation around the set of plane lines sections. The functionality of modern GIS-based data management systems is very demanding. A comprehensive application of filters by “areas of interests” requires the selection of corresponding data (i.e. seismic data in terms of our tasks) according to predefined spatial criteria. Unambiguously solved “contouring” task provides maximal effectiveness of those filters work. Moreover, implementation of the algorithm allows automating technological QC of seismic data and simplifies seismic data retrieving mechanisms based on up-to-date criteria requested by G&G data management systems.


1. Iukanova, E.A. Tekhnologiia sistematizatsii geologo-geofizicheskoi informatsii dlia tsifrovogo geologicheskogo modelirovaniia krupnykh dlitel'no razrabatyvaemykh mestorozhdenii (Avtoref. diss. dokt.) [Technology of geological and geophysical data systematization for digital modelling of large long time developing fields (Extended Abstract of Doct. Sci. Diss.)]. Moscow, 2009. 152 p. (in Russian).

2. Polovinkin, E.S, Balashov, M.V. Elementy vypuklogo i sil'no vypuklogo analiza [Elements of convex and strongly convex analysis]. Moscow, 2004. 416 p. (in Russian).

3. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C. Introduction to algorithms (3rd ed.). Massachusetts Institute of Technology: MIT Press, 2009. 1313 p.

4. Mount, D. M. Computational Geometry. University of Maryland, 2002. 122 p.

5. Barber, C.B., Dobkin, D.P., Huhdanpaa, H. The Quickhull Algorithm for Convex Hulls. ACM Transactions on Mathematical Software. 1996. Vol. 22. Issue 4. Pp. 469-483.

6. Edelsbrunner, H. Alpha Shapes — a Survey. Departments of Computer Science and of Mathematics. Durham: Duke University, 2011. 25 p.

7. Preparata, F., Sheimos, M. Vychislitel'naia geometriia: vvedenie [Computational geometry: introduction] / Transl. fr. Eng. by S.A. Viches, M.M. Komarov. Moscow, 1989. 478 p. (in Russian).

8. Moreira, A.J.C., Santos, Y.M. Concave hull: A k-nearest neighbors approach for the

computation of the region occupied by a set of points: Proc. of International Conference on Computer Graphics Theory and Applications. Barcelona, 2007.

9. Computational Geometry Algorithms Library. URL: http://www.cgal.org (date accessed: 15.12.2013).

10. Park, J-S., Oh, S-J. A new Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets. Journal of Information Science and Engineering. 2013. Vol. 29. Issue 2. Pp. 379-392. (March 2013).