Современные открытые проблемы в дискретной и вычислительной геометрии
https://doi.org/10.18255/1818-1015-2012-5-5-17
Аннотация
Авторы отобрали задачи, которые пока не так уж хорошо известны, однако способны стимулировать исследования в ряде интересных направлений. В частности, их формулировка не требует специальных знаний, выходящих за рамки стандартного круга понятий дискретной геометрии. Несмотря на относительно простые постановки, эти задачи связаны с современными исследованиями, а их решение, по-видимому, потребует новых идей и подходов. Авторы собрали задачи из разных областей, чтобы привлечь внимание широкого круга специалистов к этой короткой статье. Статья публикуется в авторской редакции.
При поддержке: Правительство Российской Федерации, грант Президента Российской Федерации
Об авторах
Герберт Эдельсбруннер
Австрийский Институт Науки и Технологий (Institute of Science and Technology, Klosterneuburg, Austria);
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
Клостенойбург, Австрия;
руководитель Международной лаборатории "Дискретная и вычислительная геометрия" им. Б.Н. Делоне
Александр Иванов
Московский государственный университет имени М.В. Ломоносова;
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
Механико-математический факультет;
научный сотрудник Международной лаборатории "Дискретная и вычислительная геометрия" им. Б.Н. Делоне
Роман Карасев
Московский физико-технический институт;
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
кафедра высшей математики;
научный сотрудник Международной лаборатории "Дискретная и вычислительная геометрия" им. Б.Н. Делоне
Список литературы
1. R. L. Adler, The Geometry of Random Fields, John Wiley & Sons, Chichester, England, 1981.
2. H. Edelsbrunner and J. L. Harer, Computational Topology. An Introduction, Amer. Math. Soc., Providence, Rhode Island, 2010.
3. 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.
4. A. B. Buda, T. Auf der Heyde and K. Mislow, “On quantifying chirality,” Angew. Chem. 31 (1992), 989–1007.
5. A. B. Buda and K. Mislow, “On a measure of axiality for triangular domains,” Elem. Math. 46 (1999), 65–73.
6. B. Gr¨unbaum, “Measures of symmetry for convex sets,” in Proc. Sympos. Pure Math., Amer. Math. Soc. 7 (1963), 233–270.
7. M. K. Hu, “Visual pattern recognition by moment invariants.” IEEE Trans. Inform. Theory 8 (1962), 179–187.
8. B. Aronov and A. Hubard, “Convex equipartitions of volume and surface area,” http://arxiv.org/abs/1010.4611, arXiv:1010.4611 (2010).
9. I. B´ar´any, “A generalization of Carath´eodory’s theorem,” Discrete Math. 40:2–3 (1982), 141–152.
10. I. B´ar´any, P. Blagojevi´c and A. Sz˝ucs, “Equipartitioning by a convex 3-fan,” Adv. Math. 223:2 (2010), 579–593.
11. M. Bern and D. Eppstein, “Worst-case bounds for subadditive geometric graphs,” in Proc. 9th Ann. Sympos. Comput. Geom. (1993), 183–188.
12. E. Boros, Z. F¨uredi, “The number of triangles covering the center of an n-set,” Geom. Dedicata 17:1 (1984), 69–77.
13. J. Pach, “A Tverberg-type result on multicolored simplices,” Comput. Geom. 10:2 (1998), 71–76.
14. C. G. A. Harnack, “Uber Vieltheiligkeit der ebenen algebraischen Curven,” ¨ Math. Ann. 10 (1876), 189–199.
15. 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.
16. R. N. Karasev, “Equipartition of several measures,” http://arxiv.org/abs/1011.4762, arXiv:1011.4762 (2010).
17. 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.
18. 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.
19. R. Nandakumar and N. Ramana Rao, “‘Fair’ partitions of polygons – an introduction,” http://arxiv.org/abs/0812.2241, arXiv:0812.2241 (2008).
20. 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).
21. P. Sober´on, “Balanced convex partitions of measures in Rd,” http://arxiv.org/abs/1010.6191, arXiv:1010.6191 (2010).
22. 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.
23. A.H. Stone and J.W. Tukey, “Generalized ’sandwich’ theorems,” Duke Math. J. 9 (1942), 356–359.
24. 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.]
25. 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].
26. N. Innami and S. Naya, “A comparison theorems for Steiner minimum trees in surfaces with curvature bounded below,” Tohoku Math. Journal (2012), to appear.
27. A. O. Ivanov and A. A. Tuzhilin, Extreme Networks Theory, Moscow, Izhevsk: Inst. of Komp. Issl. (2003) [in Russian].
28. L. Vesely, “A characterization of reflexivity in the terms of the existence of generalized centers,” Extracta Mathematicae 8:2–3 (1993), 125 – 131.
29. 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].
30. B. B. Bednov and N. P. Strelkova, “On the existence problem for shortest networks in Banach spaces,” to appear in Mat. zametki (2013).
31. 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.
32. A. O. Ivanov and A. A. Tuzhilin, Branching Solutions to One-Dimensional Variational Problems, Singapore, New Jersey, London, Hong Kong: World Scientific, 2000.
33. 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].
34. 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].
35. K. J. Swanepoel, “The local Steiner problem in normed planes”, Networks 36:2 (2000), 104-–113.
36. 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].
37. 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].
38. A. O. Ivanov and A. A. Tuzhilin, “One-dimensional Gromov minimal filling”, arXiv:1101.0106v2 [math.MG] (2011).
39. 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].
Рецензия
Для цитирования:
Эдельсбруннер Г., Иванов А., Карасев Р. Современные открытые проблемы в дискретной и вычислительной геометрии. Моделирование и анализ информационных систем. 2012;19(5):5-17. https://doi.org/10.18255/1818-1015-2012-5-5-17
For citation:
Edelsbrunner H., Ivanov A., Karasev R. Current Open Problems in Discrete and Computational Geometry. Modeling and Analysis of Information Systems. 2012;19(5):5-17. https://doi.org/10.18255/1818-1015-2012-5-5-17
Просмотров: 1192
Послать статью по эл. почте 