phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2023 - 3 issue » pp. 402-415

Archive of Issues

Russia Moscow
Year
2023
Volume
33
Issue
3
Pages
402-415
<<
>>
Section Mathematics
Title On a cube and subspace projections
Author(-s) Boykov A.A.a, Seliverstov A.V.b
Affiliations MIREA - Russian Technological Universitya, Institute for Information Transmission Problems, Russian Academy of Sciencesb
Abstract We consider the arrangement of vertices of a unit multidimensional cube, an affine subspace, and its orthogonal projections onto coordinate subspaces. Upper and lower bounds on the subspace dimension are given under which some orthogonal projection always preserves the incidence relation between the subspace and cube vertices. Some oblique projections are also considered. Moreover, a brief review of the history of the development of multidimensional descriptive geometry is given. Analytic and synthetic methods in geometry diverged since the 17th century. Although both synthesis and analysis are tangled, from this time forth many geometers as well as engineers keep up a nice distinction. One can find references to the idea of higher-dimensional spaces in the 18th-century works, but proper development has been since the middle of the 19th century. Soon such works have appeared in Russian. Next, mathematicians generalized their theories to many dimensions. Our new results are obtained by both analytic and synthetic methods. They illustrate the complexity of pseudo-Boolean programming problems because reducing the problem dimension by orthogonal projection meets obstacles in the worst case.
Keywords multidimensional cube, affine subspace, projection, discrete optimization, history of mathematics
UDC 514.142
MSC 51A15, 51N05
DOI 10.35634/vm230302
Received 10 January 2023
Language Russian
Citation Boykov A.A., Seliverstov A.V. On a cube and subspace projections, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2023, vol. 33, issue 3, pp. 402-415.
References
  1. Seliverstov A.V. Binary solutions to large systems of linear equations, Prikladnaya Diskretnaya Matematika, 2021, no. 52, pp. 5-15 (in Russian). https://doi.org/10.17223/20710410/52/1
  2. Antonopoulos A., Pagourtzis A., Petsalakis S., Vasilakis M. Faster algorithms for $k$-subset sum and variations, Journal of Combinatorial Optimization, 2023, vol. 45, issue 1, article number: 24. https://doi.org/10.1007/s10878-022-00928-0
  3. Cacchiani V., Iori M., Locatelli A., Martello S. Knapsack problems — An overview of recent advances. Part I: Single knapsack problems, Computers and Operations Research, 2022, vol. 143, 105692. https://doi.org/10.1016/j.cor.2021.105692
  4. Cacchiani V., Iori M., Locatelli A., Martello S. Knapsack problems — An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems, Computers and Operations Research, 2022, vol. 143, 105693. https://doi.org/10.1016/j.cor.2021.105693
  5. D'Ambrosio C., Laureana F., Raiconi A., Vitale G. The Knapsack Problem with forfeit sets, Computers and Operations Research, 2023, vol. 151, 106093. https://doi.org/10.1016/j.cor.2022.106093
  6. Jozefiak A., Shepherd F.B., Weninger N. A knapsack intersection hierarchy, Operations Research Letters, 2023, vol. 51, issue 1, pp. 72-78. https://doi.org/10.1016/j.orl.2022.12.001
  7. Alon T., Halman N. Strongly polynomial FPTASes for monotone dynamic programs, Algorithmica, 2022, vol. 84, issue 10, pp. 2785-2819. https://doi.org/10.1007/s00453-022-00954-8
  8. Leontiev V.K., Gordeev E.N. On the number of solutions to a system of Boolean equations, Automation and Remote Control, 2021, vol. 82, issue 9, pp. 1581-1596. https://doi.org/10.1134/S000511792109006X
  9. Gordeev E.N., Leont'ev V.K. On the number of solutions to linear Diophantine equation and Frobenius problem, Computational Mathematics and Mathematical Physics, 2022, vol. 62, issue 9, pp. 1413-1423. https://doi.org/10.1134/S0965542522090044
  10. Buekenhout F. (ed.) Handbook of incidence geometry: Buildings and foundations, North Holland, 1995. https://doi.org/10.1016/B978-0-444-88355-1.X5000-2
  11. Petunin A.A., Chentsov A.G., Chentsov P.A. Some applications of optimization routing problems with additional constraints, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2022, vol. 32, issue 2, pp. 187-210. https://doi.org/10.35634/vm220203
  12. Chentsov A.G., Chentsov A.A. Dynamic programming and questions of solvability of route bottleneck problem with resource constraints, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2022, vol. 32, issue 4, pp. 569-592 (in Russian). https://doi.org/10.35634/vm220406
  13. Devadoss S.L., Harvey M. Unfoldings and nets of regular polytopes, Computational Geometry, 2023, vol. 111, 101977. https://doi.org/10.1016/j.comgeo.2022.101977
  14. Rozenfel'd B.A., Yushkevich A.P. Geometry, Istoriya matematiki (History of mathematics), vol. 3, Moscow: Nauka, 1970, pp. 153-221.
  15. Polo-Blanco I. Alicia Boole Stott, a geometer in higher dimension, Historia Mathematica, 2008, vol. 35, issue 2, pp. 123-139. https://doi.org/10.1016/j.hm.2007.10.008
  16. Gulak N. Opyt geometrii o chetyrekh izmereniyakh. Geometriya sinteticheskaya (Essay on geometry of four dimensions. Synthetic geometry), Tiflis: S.G. Melikov publ., 1877.
  17. Lorenat J. Synthetic and analytic geometries in the publications of Jakob Steiner and Julius Plücker (1827-1829), Archive for History of Exact Sciences, 2016, vol. 70, issue 4, pp. 413-462. https://doi.org/10.1007/s00407-015-0174-8
  18. Del Centina A. Desargues's concepts of involution and transversal, their origin, and possible sources of inspiration, Archive for History of Exact Sciences, 2022, vol. 76, issue 6, pp. 573-622. https://doi.org/10.1007/s00407-022-00296-5
  19. Cerroni C. Non-Desarguian geometries and the foundations of geometry from David Hilbert to Ruth Moufang, Historia Mathematica, 2004, vol. 31, issue 3, pp. 320-336. https://doi.org/10.1016/S0315-0860(03)00049-1
  20. Vorob'eva V.P., Zelenaya A.E., Lutsyk V.I. Using a 3D computer model of the $T$–$x$–$y$ diagram of the ZrO$_2$–SiO$_2$–Al$_2$O$_3$ system to resolve contradictions in the initial experimental data, Russian Journal of Inorganic Chemistry, 2021, vol. 66, issue 6, pp. 894-901. https://doi.org/10.1134/S003602362106022X
  21. Vorob'eva V.P., Zelenaya A.E., Lutsyk V.I., Sineva S.I., Starykh R.V., Novozhilova O.S. High-temperature area of the Fe–Ni–Co–Cu phase diagram: experimental study and computer design, Journal of Phase Equilibria and Diffusion, 2021, vol. 42, issue 2, pp. 175-193. https://doi.org/10.1007/s11669-021-00863-3
  22. Lutsyk V.I., Vorob'eva V.P., Zelenaya A.E., Lamueva M.V. 3D computer model of the Co–Cu–CoS–Cu$_2$S subsystem $T$–$x$–$y$ diagram above 800°C, Journal of Mining and Metallurgy, Section B: Metallurgy, 2021, vol. 57, issue 3, pp. 319-329. https://doi.org/10.2298/JMMB190307028L
  23. Fedorov E.S. Opérations graphiques avec quatre variables indépendantes, Bulletin de l'Académie des Sciences de Russie. VI série, 1918, vol. 12, issue 7, pp. 615-624 (in Russian). https://www.mathnet.ru/eng/im5928
  24. Lodochnikov V.N. The simplest ways to represent multicomponent systems, Izvestiya Instituta Fiziko-Khimicheskogo Analiza, 1924, vol. 2, issue 2, pp. 255-351 (in Russian).
  25. Radiščev V.P. Méthodes de représentation des systèmes à six composants dans les projections des figures régulières polydimensionales, Annales du Secteur d'Analyse Physico-Chimique, 1941, vol. 14, pp. 153-173 (in Russian).
  26. Vachnadze G.A. Some problems of descriptive geometry of four-dimensional space, Trudy Gruzinskogo Politekhnicheskogo Instituta, 1955, no. 2 (37), pp. 193-214 (in Russian). https://cat.webtute.ru/pub.php?id=9401
  27. Mordukhai-Boltovskii D.D. Parallelism and perpendicularity of straight lines, planes and hyperplanes in three-dimensional and four-dimensional Lobachevskii spaces, Uspekhi Matematicheskikh Nauk, 1951, vol. 6, issue 4 (44), pp. 176-183 (in Russian). https://www.mathnet.ru/eng/rm6871
  28. Pervikova V.N., Naumovich N.V., Dmitrenko G.E., Zaytseva E.P., Podylina M.G. Multidimensional descriptive geometry and geometric methods for studying multicomponent systems, Trudy Moskovskogo Nauchno-Metodicheskogo Seminara po Nachertatel'noi Geometrii i Inzhenernoi Grafike [Issue 3]. Trudy Moskovskogo Aviatsionnogo Instituta Imeni S. Ordzhonikidze, Moscow: Moscow Aviation Institute, 1972, issue 242, pp. 23-34 (in Russian). https://cat.webtute.ru/pub.php?id=2333
  29. Dzhaparidze I.S. Independent planar models of four-dimensional space, Trudy Gruzinskogo Politekhnicheskogo Instituta, 1965, no. 1 (99), pp. 31-46 (in Russian). https://cat.webtute.ru/pub.php?id=9565
  30. Dzhaparidze I.S. Nachertatel'naya geometriya v svete geometricheskogo modelirovaniya (Descriptive geometry in the light of geometric modeling), Tbilisi: Ganatleba, 1983.
  31. Filippov P.V. Nachertatel'naya geometriya mnogomernogo prostranstva i ee prilozheniya (Descriptive geometry of multidimensional space and its applications), Leningrad: Leningrad State University, 1979.
  32. Val'kov K.I. On the interpretation of projective transformations of the four-dimensional space in the two-dimensional plane, XVIII Nauchnaya Konferentsiya Leningradskogo Inzhenerno-Stroitel'nogo Instituta. Doklady, Leningrad: Leningrad Institute of Civil Engineering, 1960, issue 18, pp. 55-60 (in Russian). https://cat.webtute.ru/pub.php?id=9806
  33. Skopets Z.A., Peklich V.A. Symplectic geometry, and Lie circular transformations, Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 1973, no. 1, pp. 91-98 (in Russian). https://www.mathnet.ru/eng/ivm4178
  34. Peklich V.A. Vysshaya nachertatel'naya geometriya (Higher descriptive geometry), Moscow: ASV, 2000.
  35. Volkov V.Ya., Chizhik M.A. Graficheskie optimizatsionnye modeli mnogofaktornykh protsessov (Graphic optimization models of multifactorial processes), Omsk: Omsk State Institute of Service, 2009.
  36. Voloshinov D.V. Konstruktivnoe geometricheskoe modelirovanie: teoriya, praktika, avtomatizatsiya (Constructive geometric modeling: theory, practice, automation), Saarbrücken: LAP Lambert Academic Publishing, 2011.
  37. Vertinskaya N.D. Matematicheskoe modelirovanie mnogofaktornykh i mnogoparametricheskikh protsessov v mnogokomponentnykh sistemakh na baze konstruktivnoi geometrii (Mathematical modeling of multifactorial and multiparameter processes in multicomponent systems based on constructive geometry), Irkutsk: Irkutsk State Technical University, 2009.
  38. Boykov A.A., Shulajkin D.A. Visualization of geometric figures and relations of a complex plane by means of computer graphics, Problemy Kachestva Graficheskoi Podgotovki Studentov v Tekhnicheskom Vuze: Traditsii i Innovatsii, 2019, vol. 1, pp. 72-93 (in Russian). https://www.elibrary.ru/item.asp?id=41429443
  39. Boykov A.A., Orlova E.V., Chernova A.V., Shkilevich A.A. Creating fractal images for design and polygraphy and some geometric generalizations associated with them, Problemy Kachestva Graficheskoi Podgotovki Studentov v Tekhnicheskom Vuze: Traditsii i Innovatsii, 2019, vol. 1, pp. 325-339 (in Russian). https://www.elibrary.ru/item.asp?id=41429476
  40. Kogabaev N.T. On closure of configurations in freely generated projective planes, Siberian Electronic Mathematical Reports, 2021, vol. 18, issue 1, pp. 358-368. https://doi.org/10.33048/semi.2021.18.025
Full text
/doc/issues-2023/23-03-02.pdf
<< Previous article
Next article >>