|
Article information
2019 , Volume 24, ¹ 4, p.28-37
Kireev T.F., Bulgakova G.T.
Construction of the Voronoi diagram with constraints on a plane
Purpose. The problem of construction the Voronoi diagram with constrains on a plane, also known as the generalized inverse Voronoi problem, is considered. The problem is to construct a Voronoi diagram on the plane, which edges lie on a given set of segments. Methodology. Constructing a Voronoi diagram with constraints is based on the formation of a set of circles and the placement of sites of the diagram at the intersections of these circles. The procedure for constructing a diagram is described by a formal language to prove its correctness. Findings. An algorithm for constructing a constrained Voronoi diagram with proof of correctness is proposed. A procedure for constructing a two-dimensional computational grid based on such a diagram is described. Value. The proposed algorithm is rather brief and has a simple proof of correctness. The use of such a grid can improve the accuracy of the numerical solution of some problems in fluid mechanics.
[full text] [link to elibrary.ru]
Keywords: Voronoi diagram, inverse Voronoi problem, planar mesh
doi: 10.25743/ICT.2019.24.4.003
Author(s):
Kireev Timur Faritovich
Position: Student
Office: Ufa State Aviation Technical University
Address: 450008, Russia, Ufa, Ufa, K. Marx street, 12
Phone Office: (347) 273-77-35
E-mail: kireevtf@mail.ru
Bulgakova Guzel Talgatovna
Dr. , Professor
Position: Student
Office: Ufa State Aviation Technical University
Address: 450008, Russia, Ufa, Ufa, K. Marx street, 12
Phone Office: (347) 273-77-35
E-mail: bulgakova.guzel@mail.ru
SPIN-code: 6764-2200 References:
[1] Shewchuk, J.R. Delaunay refinement algorithms for triangular mesh generation. Computational Geometry. 2002; 22(1 -3):21–74.
[2] Lo, S.H. Finite element mesh generation. London: CRC Press; 2014: 672. ISBN: 9781482266870.
[3] Frey, P. J., George, P.L. Mesh generation: application to finite elements. 2nd Edition. London: ISTE& Wiley LTD; 2008: 848.
[4] Palagi, C.L., Aziz, K. Use of voronoi grid in reservoir simulation. SPE Advanced Technology Series. 1994; 2(2):69–77.
[5] Branets, L.V., Ghai, S.S., Lyons, S.L., Wu, X.H. Efficient and accurate reservoir modeling using adaptive gridding with global scale up. Proceedings of SPE Reservoir Simulation Symposium. 2009: 11. SPE118946 doi: 10.2118/118946-MS.
[6] Yan, D., Wang, W., Lévy, B., Liu Y. Efficient computation of clipped Voronoi diagram for mesh generation. Computer- Aided Design. 2013; 45(4):843–852.
[7] Aloupis, G., Perez-Roses, H., Pineda-Villavicencio, G., Taslakian, P., Trinchet-Almaguer, D. Fitting Voronoi diagrams to planar tessellations. International Workshop on Combinatorial Algorithms IWOCA 2013: Combinatorial Algorithms. Heidelberg; 2013: 349–361.
[8] Banerjee, S., Bhattacharya, B.B., Das, S., Karmakar, A., Maheshwari, A., Roy, S. On the construction of a generalized Voronoi inverse of a rectangular Tesselation. In: Procs. 9th Int. IEEE Symposium on Voronoi Diagrams in Science and Engineering. IEEE, New Brunswick, NJ; 2012: 132-137.
[9] Berge, R.L. Unstructured pebi grids adapting to geological feautres in subsurface reservoirs. Master’s thesis. Norwegian University of Science and Technology; 2016: 105.
[10] Abdelkader, A., Bajaj, C.L., Ebeida, M.S., Mitchell, S.A. A seed placement strategy for conforming Voronoi meshing. Proceedings of 29th Canadian Conference on Computational Geometry. CCCG 2017, Ottawa, Ontario, July 26–28. 2017: 95–100.
Bibliography link:
Kireev T.F., Bulgakova G.T. Construction of the Voronoi diagram with constraints on a plane // Computational technologies. 2019. V. 24. ¹ 4. P. 28-37
|
