maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2012-5-5-17mais-51Research ArticleОригинальные статьиArticlesСовременные открытые проблемы в дискретной и вычислительной геометрииCurrent Open Problems in Discrete and Computational GeometryЭдельсбруннерГербертEdelsbrunnerH.

Клостенойбург, Австрия;

руководитель Международной лаборатории "Дискретная и вычислительная геометрия" им. Б.Н. Делоне

edels@ist.ac.atИвановАлександрIvanovA.

Механико-математический факультет;

научный сотрудник Международной лаборатории "Дискретная и вычислительная геометрия" им. Б.Н. Делоне

aoiva@mech.math.msu.suКарасевРоманKarasevR.

кафедра высшей математики;

научный сотрудник Международной лаборатории "Дискретная и вычислительная геометрия" им. Б.Н. Делоне

r_n_karasev@mail.ruАвстрийский Институт Науки и Технологий (Institute of Science and Technology, Klosterneuburg, Austria); Ярославский государственный университет им. П.Г. ДемидоваРоссияInstitute of Science and Technology Austria; P.G. Demidov Yaroslavl State UniversityRussian FederationМосковский государственный университет имени М.В. Ломоносова; Ярославский государственный университет им. П.Г. ДемидоваРоссияMoscow State University; P.G. Demidov Yaroslavl State UniversityRussian FederationМосковский физико-технический институт; Ярославский государственный университет им. П.Г. ДемидоваРоссияMoscow Institute of Physics and Technology; P.G. Demidov Yaroslavl State UniversityRussian Federation201204032015195517Copyright © Эдельсбруннер Г., Иванов А., Карасев Р., 20152015Эдельсбруннер Г., Иванов А., Карасев Р.Edelsbrunner H., Ivanov A., Karasev R.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/51

Авторы отобрали задачи, которые пока не так уж хорошо известны, однако способны стимулировать исследования в ряде интересных направлений. В частности, их формулировка не требует специальных знаний, выходящих за рамки стандартного круга понятий дискретной геометрии. Несмотря на относительно простые постановки, эти задачи связаны с современными исследованиями, а их решение, по-видимому, потребует новых идей и подходов. Авторы собрали задачи из разных областей, чтобы привлечь внимание широкого круга специалистов к этой короткой статье. Статья публикуется в авторской редакции.

We have selected problems that may not yet be well known, but have the potential to push the research in interesting directions. In particular, we state problems that do not require specific knowledge outside the standard circle of ideas in discrete geometry. Despite the relatively simple statements, these problems are related to current research and their solutions are likely to require new ideas and approaches. We have chosen problems from different fields to make this short paper attractive to a wide range of specialists.

The article is published in the author’s wording.

дискретная и вычислительная геометриявычислительная топологияоткрытые проблемыdiscrete and computational geometrycomputational topologyopen problemsПравительство Российской Федерации, грант Президента Российской ФедерацииReferencesR. L. Adler, The Geometry of Random Fields, John Wiley & Sons, Chichester, England, 1981.R. L. Adler, The Geometry of Random Fields, John Wiley & Sons, Chichester, England, 1981.H. Edelsbrunner and J. L. Harer, Computational Topology. An Introduction, Amer. Math. Soc., Providence, Rhode Island, 2010.H. Edelsbrunner and J. L. Harer, Computational Topology. An Introduction, Amer. Math. Soc., Providence, Rhode Island, 2010.A. J. S. Hamilton, J. R. Gott III and D. Weinberg, “The topology of the large-scale structure of the Universe,” The Astrophys. J. 309 (1986), 1–12.A. J. S. Hamilton, J. R. Gott III and D. Weinberg, “The topology of the large-scale structure of the Universe,” The Astrophys. J. 309 (1986), 1–12.A. B. Buda, T. Auf der Heyde and K. Mislow, “On quantifying chirality,” Angew. Chem. 31 (1992), 989–1007.A. B. Buda, T. Auf der Heyde and K. Mislow, “On quantifying chirality,” Angew. Chem. 31 (1992), 989–1007.A. B. Buda and K. Mislow, “On a measure of axiality for triangular domains,” Elem. Math. 46 (1999), 65–73.A. B. Buda and K. Mislow, “On a measure of axiality for triangular domains,” Elem. Math. 46 (1999), 65–73.B. Gr¨unbaum, “Measures of symmetry for convex sets,” in Proc. Sympos. Pure Math., Amer. Math. Soc. 7 (1963), 233–270.B. Gr¨unbaum, “Measures of symmetry for convex sets,” in Proc. Sympos. Pure Math., Amer. Math. Soc. 7 (1963), 233–270.M. K. Hu, “Visual pattern recognition by moment invariants.” IEEE Trans. Inform. Theory 8 (1962), 179–187.M. K. Hu, “Visual pattern recognition by moment invariants.” IEEE Trans. Inform. Theory 8 (1962), 179–187.B. Aronov and A. Hubard, “Convex equipartitions of volume and surface area,” http://arxiv.org/abs/1010.4611, arXiv:1010.4611 (2010).B. Aronov and A. Hubard, “Convex equipartitions of volume and surface area,” http://arxiv.org/abs/1010.4611, arXiv:1010.4611 (2010).I. B´ar´any, “A generalization of Carath´eodory’s theorem,” Discrete Math. 40:2–3 (1982), 141–152.I. B´ar´any, “A generalization of Carath´eodory’s theorem,” Discrete Math. 40:2–3 (1982), 141–152.I. B´ar´any, P. Blagojevi´c and A. Sz˝ucs, “Equipartitioning by a convex 3-fan,” Adv. Math. 223:2 (2010), 579–593.I. B´ar´any, P. Blagojevi´c and A. Sz˝ucs, “Equipartitioning by a convex 3-fan,” Adv. Math. 223:2 (2010), 579–593.M. Bern and D. Eppstein, “Worst-case bounds for subadditive geometric graphs,” in Proc. 9th Ann. Sympos. Comput. Geom. (1993), 183–188.M. Bern and D. Eppstein, “Worst-case bounds for subadditive geometric graphs,” in Proc. 9th Ann. Sympos. Comput. Geom. (1993), 183–188.E. Boros, Z. F¨uredi, “The number of triangles covering the center of an n-set,” Geom. Dedicata 17:1 (1984), 69–77.E. Boros, Z. F¨uredi, “The number of triangles covering the center of an n-set,” Geom. Dedicata 17:1 (1984), 69–77.J. Pach, “A Tverberg-type result on multicolored simplices,” Comput. Geom. 10:2 (1998), 71–76.J. Pach, “A Tverberg-type result on multicolored simplices,” Comput. Geom. 10:2 (1998), 71–76.C. G. A. Harnack, “Uber Vieltheiligkeit der ebenen algebraischen Curven,” ¨ Math. Ann. 10 (1876), 189–199.C. G. A. Harnack, “Uber Vieltheiligkeit der ebenen algebraischen Curven,” ¨ Math. Ann. 10 (1876), 189–199.M. Gromov, “Singularities, expanders, and topology of maps. Part 2: from combinatorics to topology via algebraic isoperimetry,” Geometric and Functional Analysis 20:2 (2010), 416–526.M. Gromov, “Singularities, expanders, and topology of maps. Part 2: from combinatorics to topology via algebraic isoperimetry,” Geometric and Functional Analysis 20:2 (2010), 416–526.R. N. Karasev, “Equipartition of several measures,” http://arxiv.org/abs/1011.4762, arXiv:1011.4762 (2010).R. N. Karasev, “Equipartition of several measures,” http://arxiv.org/abs/1011.4762, arXiv:1011.4762 (2010).R. N. Karasev, “A simpler proof of the Boros–F¨uredi–B´ar´any–Pach–Gromov theorem,” Discrete Comput. Geom. 47:3 (2012), 492–495.R. N. Karasev, “A simpler proof of the Boros–F¨uredi–B´ar´any–Pach–Gromov theorem,” Discrete Comput. Geom. 47:3 (2012), 492–495.H. Kaplan, J. Matouˇsek and M. Sharir, “Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique,” Discrete Comput. Geom. 48:3 (2012), 499–517.H. Kaplan, J. Matouˇsek and M. Sharir, “Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique,” Discrete Comput. Geom. 48:3 (2012), 499–517.R. Nandakumar and N. Ramana Rao, “‘Fair’ partitions of polygons – an introduction,” http://arxiv.org/abs/0812.2241, arXiv:0812.2241 (2008).R. Nandakumar and N. Ramana Rao, “‘Fair’ partitions of polygons – an introduction,” http://arxiv.org/abs/0812.2241, arXiv:0812.2241 (2008).J. Matouˇsek and U. Wagner, “On Gromov’s method of selecting heavily covered points,” http://arxiv.org/abs/1102.3515, arXiv:1102.3515 (2011).J. Matouˇsek and U. Wagner, “On Gromov’s method of selecting heavily covered points,” http://arxiv.org/abs/1102.3515, arXiv:1102.3515 (2011).P. Sober´on, “Balanced convex partitions of measures in Rd,” http://arxiv.org/abs/1010.6191, arXiv:1010.6191 (2010).P. Sober´on, “Balanced convex partitions of measures in Rd,” http://arxiv.org/abs/1010.6191, arXiv:1010.6191 (2010).H. Steinhaus, “Sur la division des ensembles de l’espaces par les plans et des ensembles plans par les cercles,” Fund. Math. 33 (1945), 245–263.H. Steinhaus, “Sur la division des ensembles de l’espaces par les plans et des ensembles plans par les cercles,” Fund. Math. 33 (1945), 245–263.A.H. Stone and J.W. Tukey, “Generalized ’sandwich’ theorems,” Duke Math. J. 9 (1942), 356–359.A.H. Stone and J.W. Tukey, “Generalized ’sandwich’ theorems,” Duke Math. J. 9 (1942), 356–359.V.A. Vasil’ev, “Braid group cohomologies and algorithm complexity,” Funkts. Anal. Prilozh. 22:3 (1988), 15–24 [Funct. Anal. Appl. 22:3 (1988), 182–190.]V.A. Vasil’ev, “Braid group cohomologies and algorithm complexity,” Funkts. Anal. Prilozh. 22:3 (1988), 15–24 [Funct. Anal. Appl. 22:3 (1988), 182–190.]A. O. Ivanov and A. A. Tuzhilin, “Geometry of minimal networks and onedimensional Plateau problem,” Uspekhi matem. nauk 47:2 (1992), 53–115 [Russian Math. Surveys 47:2 (1992), pp. 59–131].A. O. Ivanov and A. A. Tuzhilin, “Geometry of minimal networks and onedimensional Plateau problem,” Uspekhi matem. nauk 47:2 (1992), 53–115 [Russian Math. Surveys 47:2 (1992), pp. 59–131].N. Innami and S. Naya, “A comparison theorems for Steiner minimum trees in surfaces with curvature bounded below,” Tohoku Math. Journal (2012), to appear.N. Innami and S. Naya, “A comparison theorems for Steiner minimum trees in surfaces with curvature bounded below,” Tohoku Math. Journal (2012), to appear.A. O. Ivanov and A. A. Tuzhilin, Extreme Networks Theory, Moscow, Izhevsk: Inst. of Komp. Issl. (2003) [in Russian].A. O. Ivanov and A. A. Tuzhilin, Extreme Networks Theory, Moscow, Izhevsk: Inst. of Komp. Issl. (2003) [in Russian].L. Vesely, “A characterization of reflexivity in the terms of the existence of generalized centers,” Extracta Mathematicae 8:2–3 (1993), 125 – 131.L. Vesely, “A characterization of reflexivity in the terms of the existence of generalized centers,” Extracta Mathematicae 8:2–3 (1993), 125 – 131.P. A. Borodin, “An example of nonexistence of a Steiner point in a Banach space,” Mat. Zametki 87:4 (2010), 514–518 [Math. Notes 87:4 (2010), 485–488].P. A. Borodin, “An example of nonexistence of a Steiner point in a Banach space,” Mat. Zametki 87:4 (2010), 514–518 [Math. Notes 87:4 (2010), 485–488].B. B. Bednov and N. P. Strelkova, “On the existence problem for shortest networks in Banach spaces,” to appear in Mat. zametki (2013).B. B. Bednov and N. P. Strelkova, “On the existence problem for shortest networks in Banach spaces,” to appear in Mat. zametki (2013).V. Kadets, “Under a suitable renorming every nonreflexive Banach space has a finite subset without a Steiner point,” Matematychni Studii 36:2 (2011), 197 – 200.V. Kadets, “Under a suitable renorming every nonreflexive Banach space has a finite subset without a Steiner point,” Matematychni Studii 36:2 (2011), 197 – 200.A. O. Ivanov and A. A. Tuzhilin, Branching Solutions to One-Dimensional Variational Problems, Singapore, New Jersey, London, Hong Kong: World Scientific, 2000.A. O. Ivanov and A. A. Tuzhilin, Branching Solutions to One-Dimensional Variational Problems, Singapore, New Jersey, London, Hong Kong: World Scientific, 2000.A. O. Ivanov and A. A. Tuzhilin, “Branching geodesics in normed spaces,” Izv. RAN Ser. matem. 66:5 (2002), 33–82 [Izv. Math. 66:5 (2002), 905–948].A. O. Ivanov and A. A. Tuzhilin, “Branching geodesics in normed spaces,” Izv. RAN Ser. matem. 66:5 (2002), 33–82 [Izv. Math. 66:5 (2002), 905–948].D. P. Il’utko, “Branching extremals of the length functional in a λ-normed space,” Matem. sbornik 197:5 (2006), 75–98 [Sb. Math. 197:5 (2006), 705–726].D. P. Il’utko, “Branching extremals of the length functional in a λ-normed space,” Matem. sbornik 197:5 (2006), 75–98 [Sb. Math. 197:5 (2006), 705–726].K. J. Swanepoel, “The local Steiner problem in normed planes”, Networks 36:2 (2000), 104-–113.K. J. Swanepoel, “The local Steiner problem in normed planes”, Networks 36:2 (2000), 104-–113.A. O. Ivanov and A. A. Tuzhilin, “Steiner minimal tree uniqueness for boundaries in general position,” Matem. Sbornik 197:9 (2006),55–90 [Sb. Math. 197:9 (2006), 1309–1340].A. O. Ivanov and A. A. Tuzhilin, “Steiner minimal tree uniqueness for boundaries in general position,” Matem. Sbornik 197:9 (2006),55–90 [Sb. Math. 197:9 (2006), 1309–1340].K. L. Oblakov, “Non-existence of distinct codirected locally minimal trees on a plane,” Vestnik MGU, Ser. Matem. i Mekh. No. 2 (2009), 21–25 [Moscow University Math. Bull. 64:2 (2009), 62–66].K. L. Oblakov, “Non-existence of distinct codirected locally minimal trees on a plane,” Vestnik MGU, Ser. Matem. i Mekh. No. 2 (2009), 21–25 [Moscow University Math. Bull. 64:2 (2009), 62–66].A. O. Ivanov and A. A. Tuzhilin, “One-dimensional Gromov minimal filling”, arXiv:1101.0106v2 [math.MG] (2011).A. O. Ivanov and A. A. Tuzhilin, “One-dimensional Gromov minimal filling”, arXiv:1101.0106v2 [math.MG] (2011).A. O. Ivanov and A. A. Tuzhilin, “One-dimensional Gromov’s minimal filling problem”, Matem. Sbornik 203:5 (2012), 65–118 [Sbornik: Mathematics 203:5 (2012), 677–726].A. O. Ivanov and A. A. Tuzhilin, “One-dimensional Gromov’s minimal filling problem”, Matem. Sbornik 203:5 (2012), 65–118 [Sbornik: Mathematics 203:5 (2012), 677–726].

The authors declare that there are no conflicts of interest present.