Optimization Geometric Models and a Unified Algorithm for Tracing Engineering Networks on Planes with Different Metric

Kaiyrbek Kuspekov

doi:10.12737/2308-4898-2025-13-1-3-14

UDC 51

OPTIMIZATION GEOMETRIC MODELS AND A UNIFIED ALGORITHM FOR TRACING ENGINEERING NETWORKS ON PLANES WITH DIFFERENT METRIC Optimization Geometric Models and a Unified Algorithm for Tracing Engineering Networks on Planes with Different Metric

АА Аа

Published in Geometry & Graphics · Volume 13, Issue 1 · Pages 3–14 · Rubric: Scientific problems of geometry

DOI: https://doi.org/10.12737/2308-4898-2025-13-1-3-14

Received: 14.09.2024 Accepted: 21.07.2025 Published: 22.07.2025

Authors

Kaiyrbek Kuspekov

Academic degree: candidate of technical sciences

K.ISatpayev Kazakh National Research Technical University associate professor · Kazakhstan · Almaty

ABSTRACT

An important stage in the design of engineering networks is the development of network configurations that meet pre-defined conditions. The main thing for constructing optimization geometric models is to construct the shortest connecting lines for a given discrete set of points in space. The specified points have different weights. Such models also identify geometric factors and determine certain properties of the network configuration in the considered physical space. Geometric models define the image of the projected object and you can build various network tracing configurations that allow you to choose the optimal network. To solve this engineering problem, the article investigates and develops optimization geometric models on planes with Euclidean, orthogonal, polar metrics and algorithms. A unified algorithm for tracing extensive engineering networks on planes with different metrics has been developed. This goal is achieved by applying and generalizing the Steiner method. As you know, the Steiner problem related to the tasks of constructing a minimal spanning tree has not been solved in a general way. The practical solution to the tracing problem is to find the configuration of an extensive network with the smallest length, which has a greater impact on its cost. At the first stage of design, geometric models of engineering networks are developed, then optimization problems are solved, which are reduced to various generalizations of the problem J. Steiner [5,27]. The algorithm for solving the Steiner problem is based on dividing the given discrete points of the plane into a local subset, using the principle of least elongation and a comparative analysis of various geometric models, which allows you to select and build a network of the required configuration. A unified tracing algorithm is formulated for constructing the configuration of a Euclidean, orthogonal, and polar network. The complexity of solving the Steiner problem and engineering tracing problems is due to the fact that these problems belong to the extreme and to the class of NP-hard discrete optimization problems.

KEYWORDS

geometric models, network tracing, shortest lines, Steiner's problem, Steiner's Euclidean network, Steiner's orthogonal network, Steiner's polar network

1. Anan'ev A.A. Novyy algoritm optimizacii dizayna transportnyh setey s uchetom ogranicheniy [Tekst] / A.A. Anan'ev, P.V. Lomovickiy, D.V. Uzhegov, A.N. Hlyupin // Vychislitel'nye metody i programmirovanie. — M.: Nauchno-issledovatel'skiy vychislitel'nyy centr MGU im. M.V. Lomonosova, 2017. T. 18. — S. 158–168. — DOI:https://doi.org/10.26089/NumMet.v18r213 EDN: https://elibrary.ru/VQSUNP

2. Babayan B.A. Nahozhdenie svyazyvayuschey seti absolyutno minimal'noy dliny [Tekst] / B.A. Babayan, B.S. Popov // Tr. seminara otdela strukturnyh logicheskih shem. M.: ITM i VT AN SSSR, 1969. — Vyp. 7. — S. 27–45.

3. Bagov M.A. Nelokal'noe reshenie setevoy zadachi Shteynera [Tekst] / M.A. Bagov // Vestnik KRAUNC. Fiz.mat nauka. — 2018. — № 4. — S. 148–157. — DOIhttps://doi.org/10.18454/2079-6641- 2018-24-4-148-157 DOI: https://doi.org/10.18454/2079-6641-2018-24-4-148-157; EDN: https://elibrary.ru/VQHNBI

4. Gil'bert E.N. Minimal'nye derev'ya Shteynera [Tekst] / E.N. Gil'bert, G.O. Pollak // Kiberneticheskiy sbornik. — M.: Mir, 1974. — Vyp. 8. — S. 19–50.

5. Esmuhan Zh.M. Prikladnaya geometriya inzhenernyh setey: monografiya [Tekst] / Zh.M. Esmuhan, K.A. Kuspekov. — Almaty: Nauka, 2012. — 132 s.

6. Kel'mans A.K. O postroenii kratchayshey svyazyvayuschey seti [Tekst] / A.K. Kel'mans // Kibernetika i upravlenie. — M.: Nauka, 1967. — S. 115–130.

7. Kureychik V.V. Teoriya evolyucionnyh vychisleniy [Tekst] / V.V. Kureychik, V.M. Kureychik, S.I. Rodzin. M.: Fizmatlit, 2013. — 260 s.

8. Kureychik V.M. Gibridnyy algoritm razbieniya na osnove prirodnyh mehanizmov prinyatiya resheniy [Tekst] / V.M Kureychik., B.K. Lebedev, O.B. Lebedev // Izvestiya RAN. Iskusstvennyy intellekt i prinyatie resheniy. 2012. — S. 3–15.

9. Kureychik V.M. Planirovanie sverhbol'shih integral'nyh shem na osnove integracii modeley adaptivnogo poiska [Tekst] / V.M. Kureychik, B.K. Lebedev, V.B. Lebedev // Izvestiya RAN. Teoriya i sistemy upravleniya. 2013 — № 1. — S. 84–101.

10. Kuspekov K.A. Metod razbienie i postroeniya kratchayshih setey na ploskosti s evklidovoy metrikoy [Tekst] / K.A.Kuspekov // Materialy Mezhdunarodnoy-Vserossiyskoy 66-nauchno-prakticheskoy konferencii. 18–19 oktyabrya 2012 g. Sibirskaya gosudarstvennaya avtomobil'no-dorozhnaya akademiya (SibADI). — Omsk, 2012. — S. 178–181.

11. Kuspekov K.A. Geometricheskie metody trassirovki transportno-logisticheskih setey [Tekst] / K.A Kuspekov., S.I. Rotkov // Materialy 26-y Mezhdunarodnoy konferencii po komp'yuternoy grafike i zreniyu, GrafiKON. — 2016. — S. 531–534.12. Kuspekov K.A. Algoritm postroeniya optimal'noy konfiguracii transportnoy seti zavodov [Tekst] / K.A. Kuspekov. — Almaty: Doklady Nacional'noy akademii nauk Respubliki Kazahstan. — 2010. – № 3. S. 97–99. EDN: https://elibrary.ru/XCVXSR

12. Kuspekov K.A. Metodika postroeniya optimal'noy konfiguracii kratchayshih svyazyvayuschih linii dlya n tochek ploskosti s polyarnoy metrikoy [Tekst] / K.A. Kuspekov // Vestnik KuzGTU. — 2012. — № 2. — S. 86–87. EDN: https://elibrary.ru/OXWNON

13. Kuspekov K.A. Svidetel'stvo. Paket programm dlya EVM: Postroenie geometricheskoy modeli rascheta trassirovki seti na ploskosti s evklidovoy, ortogonal'noy i polyarnoy metrikoy primenyaemye v reshenii razlichnyh inzhenernyh zadach [Tekst] / K.A. Kuspekov, Sh.A. Dzhomartova, A.T. Mazakova. — № 1912, IS009522. Minyust RK, g. Astana. — 1 avgusta 2017.

14. Lebedev B.K. Intellektual'naya procedura postroeniya dereva Shteynera na osnove procedur otsechki i suzheniya [Tekst] / B.K. Lebedev // Izvestiya TRTU. — 2000. № 1. — S. 89. EDN: https://elibrary.ru/IJLUGZ

15. Leparov M.N. O geometricheskih osnovah proektirovaniya tehnicheskogo ob'ekta [Tekst] / M.N. Leparov // Geometriya i grafika. — 2019. — T. 7. — № 2. — S. 28–38. DOI:https://doi.org/10.12737/2308-4898-2023-11-4-3-14 DOI: https://doi.org/10.12737/article_5d2c187251b6c8.21632403; EDN: https://elibrary.ru/CFHAMF

16. Lotarev D.T. Lokal'naya optimizaciya v zadache Shteynera na evklidovoy ploskosti [Tekst] / D.T. Lotarev, A.V. Suprun, A.P. Uzdemir // Avtomatika i telemehanika. — 2004. — № 7. — S. 60–70. EDN: https://elibrary.ru/NQYVZF

17. Lotarev D.T. Zadacha Shteynera dlya transportnoy seti na poverhnosti zadannoy cifrovoy model'yu [Tekst] / D.T. Lotarev // Avtomatika i telemehanika. — 1980. № 10. — 104–115.

18. Prim R.K. Kratchayshie svyazyvayuschie seti i nekotorye obobscheniya [Tekst] / R.K. Prim // Kiberneticheskiy sbornik. — 1961. — № 2. — S. 95–107.

19. Prokof'ev V.M. Nekotorye svoystva kratchayshey linii, soedinyayuschey lyuboe chislo tochek ploskosti [Tekst] / V.M. Prokof'ev // Uchenye zapiski Mosk. gos. ped. in-ta im. V.I. Lenina. — M.: Izd-vo MGPI, 1957. Vyp. 3. — S. 53–67.

20. Sal'kov N.A. Otrazheniya razvitiya inzhenernoy geometrii v zhurnale «Geometriya i grafika» [Tekst] / N.A. Sal'kov, N.S. Kadykova // Geometriya i grafika. 2020. — T. 8. — № 2. — S. 82–100. — DOI:https://doi.org/10.12737/23084898-2020-82-100 DOI: https://doi.org/10.12737/2308-4898-2020-82-100; EDN: https://elibrary.ru/PZHJOC

21. Sal'kov N.A. Geometricheskaya sostavlyayuschaya tehnicheskih innovacii [Tekst] / N.A. Sal'kov // Geometriya i grafika. –2018. — T. 6. — № 2. — S. 85–94. — DOIhttps://doi.org/10.12737/article5b55a5163fa05307622109 DOI: https://doi.org/10.12737/article_5b55a5163fa053.07622109; EDN: https://elibrary.ru/XVRALZ

22. Chernyshev Yu.O. K voprosu o postroenii derev'ev Shteynera s razlichnoy shirinoy vetvey dlya svyazyvaniya elementov trehmernyh SBIS [Tekst] / Yu.O. Chernyshev, N.N. Vencov // Izvestiya YuFU. Tehnicheskie nauki. 2009. — № 4. — S. 72–76. EDN: https://elibrary.ru/KUWJHV

23. Boyce W.M. An improved program for the full Steiner tree problem // ACM. Trans, on Math. Software. 1977. V. 3, pp. 359–385. DOI: https://doi.org/10.1145/355759.355764

24. Chang S. The generation of minimal trees with a Steiner topology // I. ACM. 1972. V. 19, pp. 669–711. DOI: https://doi.org/10.1145/321724.321733

25. Cockayne E. J. Exact computation on Steiner minimal trees in the plane / E.J. Cockayne, E.E. Hewgill // Inf. Proc. Letters.1989. V. 22, pp. 151–156. DOI: https://doi.org/10.1016/0020-0190(86)90062-1

26. Courant R. What is Mathematics / R. Courant, H. Robbins. Oxford University Press, 1996, p. 556. DOI: https://doi.org/10.1093/oso/9780195105193.001.0001

27. Hwang F. The Steiner Tree Problem / F.K. Hwang, D.S. Richards, P. Winter // Annals of Discrete mathematics. 1992. V. 53.

28. Korhonon P. An algorithm for transfor ming a spanning tree into a Steiner // Procc. 9 th Int. Progn. Symp., Budapest 1976. North Holland, Amsterdam, 1979, pp. 343–357.

29. Kuspekov K.A. Optimization geometric models of transport network tracing used in city planning. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences — ISPRS Archives, 2023, 48(5/W2-2023), pp. 63–69. DOI: https://doi.org/10.5194/isprs-archives-xlviii-5-w2-2023-63-2023; EDN: https://elibrary.ru/MINOUX

30. Melzak S.A. On the problem of Stelner // J. Canad. Math. Bull. 1961. V. 4, pp. 143–148. DOI: https://doi.org/10.4153/CMB-1961-016-2

31. Smith I.M. An 0 (n logn) heuristic algorithm for the Steiner minimal tree problems on the euclidaen metric / I.M. Smith, D.T. Lee, I.S. Liebman // Networks. 1981. V. 11, pp. 23–29. DOI: https://doi.org/10.1002/net.3230110104

32. Trifonov A.G. Formulation of the Optimization Problem and Numerical Methods of Its Solution, http://matlab.exponenta.ru/optimiz/book_2/index.php. Cited April 24, 2017.

33. Winter P. Anargoritm for the Steiner problem in the euchlidean plane // Networks. 1985. V. 15, pp. 323–345. DOI: https://doi.org/10.1002/net.3230150305

JATS XML

Zamestitel' glavnogo redaktora, chlen redsoveta

Vladimir Vyshnyepolskiy

Glavnyy redaktor

A. A. Ishchenko

Vypuskayuschiy redaktor

Dar'ya Sklyankina

501@infra-m.ru

Deputy editor-in-chief, member of the editorial Board

N. Sal'kov

nikolaysalkov@mail.ru

GOST

Kuspekov K. A. Optimization Geometric Models and a Unified Algorithm for Tracing Engineering Networks on Planes with Different Metric // Geometry & Graphics. 2024. no. 1. pp. 3-14. DOI: https://doi.org/10.12737/2308-4898-2025-13-1-3-14. (Date of access 07.10.2026).

MLA

Kaiyrbek Kuspekov. "Optimization Geometric Models and a Unified Algorithm for Tracing Engineering Networks on Planes with Different Metric." Geometry & Graphics 13.1 (2024): 3-14. DOI: https://doi.org/10.12737/2308-4898-2025-13-1-3-14.

APA

Kuspekov K. A. (2024). Optimization Geometric Models and a Unified Algorithm for Tracing Engineering Networks on Planes with Different Metric. Geometry & Graphics, 13(1), 3-14. https://doi.org/10.12737/2308-4898-2025-13-1-3-14

Chicago

Kaiyrbek Kuspekov. "Optimization Geometric Models and a Unified Algorithm for Tracing Engineering Networks on Planes with Different Metric." Geometry & Graphics 13, no. 1 (2024): 3-14. https://doi.org/10.12737/2308-4898-2025-13-1-3-14.

WIKI

{{cite journal | author = Kuspekov K. A. | title = Optimization Geometric Models and a Unified Algorithm for Tracing Engineering Networks on Planes with Different Metric | journal = Geometry & Graphics | year = 2024 | volume = 13 | issue = 1 | pages = 3-14 | doi = 10.12737/2308-4898-2025-13-1-3-14 }}

Copy

Export: BibTeX EndNote RefMan RusMARC

OPTIMIZATION GEOMETRIC MODELS AND A UNIFIED ALGORITHM FOR TRACING ENGINEERING NETWORKS ON PLANES WITH DIFFERENT METRIC Optimization Geometric Models and a Unified Algorithm for Tracing Engineering Networks on Planes with Different Metric

Confirmation