4510
правок
Триангуляция с минимальным весом: различия между версиями
Перейти к навигации
Перейти к поиску
Триангуляция с минимальным весом (посмотреть исходный код)
Версия от 19:06, 28 сентября 2016
, 28 сентября 2016→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 40: | Строка 40: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Все вышеперечисленные подходы оставляют нерешенными некоторые вопросы. Например, можно ли найти более простое доказательство NP-полноты, которое можно проверить без исполнения компьютерных программ? Было бы желательно улучшить константный коэффициент, который может быть достигнут за полиномиальное время (для упрощения доказательства константа, представленная в работе [ ], не вычисляется явно и может быть достаточно большой, если доказательство проводится не слишком аккуратно). Есть надежда, что временную границу для схемы аппроксимации можно улучшить. Также может оказаться возможным оптимизировать алгоритмы, эффективно вычисляющие точную триангуляцию с минимальным весом для больших множеств точек, что позволит эффективно решать более широкий класс задач, а не только задачи с полностью случайными наборами точек. Возможно, этой цели можно достичь при помощи сочетания этого подхода и алгоритмов с фиксированными параметрами, как в работах [2, 4], либо иными способами. Также остается открытым вопрос, можно ли еще больше улучшить субэкспоненциальный точный метод вычисления триангуляции. | |||
== Ссылка на код == | |||
Ссылка на код, использовавшийся для сравнения некоторых подходов к динамическому программированию в [2]: http://fuzzy.cs.uni-magdeburg.de/~borgelt/pointgon.html | |||
== См. также == | |||
* ''[[Быстрая минимальная триангуляция]] | |||
* ''[[Жадные алгоритмы покрытия множества]] | |||
* ''[[Минимальные геометрические остовные деревья]] | |||
* ''[[Минимальные k-связные геометрические сети]] | |||
== Литература == | |||
1. Beirouti,R., Snoeyink, J.: Implementations of the LMT Heuristicfor Minimum Weight Triangulation. Symposium on Computational Geometry, pp. 96-105, Minneapolis, Minnesota, June 7-10,1998 | |||
2. Borgelt, C., Grantson, M., Levcopoulos, C.: Fixed-Parameter Algorithms for the Minimum Weight Triangulation Problem. | |||
Technical Report LU-CS-TR:2006-238, ISSN 1650-1276 Report 158. Lund University, Lund (An extended version has been submitted to IJCGA) (2006) | |||
3. de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry - Algorithms and Applications, 2nd edn. Springer, Heidelberg (2000) | |||
4. Grantson, M., Borgelt, C., Levcopoulos, C.: Minimum Weight Triangulation by Cutting Out Triangles. In: Proceedings 16th Annual International Symposium on Algorithms and Computation, ISAAC 2005, Sanya, China, pp. 984-994. Lecture Notes in Computer Science, vol. 3827. Springer, Heidelberg (2005) | |||
5. Gudmundsson, J., Levcopoulos, C.: A Parallel Approximation Algorithm for Minimum Weight Triangulation. Nordic J. Comput. 7(1), 32-57 (2000) | |||
6. Hjelle, 0., Daehlen, M.: Triangulations and Applications. In: Mathematics and Visualization, vol. IX. Springer, Heidelberg (2006). ISBN 978-3-540-33260-2 | |||
7. Levcopoulos, C., Krznaric, D.: Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation. J. Algorithms 27(2),303-338(1998) | |||
8. Levcopoulos, C., Krznaric, D.: The Greedy Griangulation can be Computed from the Delaunay Triangulation in Linear Time. Comput.Geom. 14(4), 197-220 (1999) | |||
9. Levcopoulos, C., Lingas, A.: On Approximation Behavior of the Greedy Triangulation for Convex Polygons. Algorithmica 2, 15-193(1987) | |||
10. Lingas, A.: Subexponential-time algorithms for minimum weight triangulations and related problems. In: Proceed ings 10th Canadian Conference on Computational Geometry (CCCG), McGill University, Montreal, Quebec, 10-12 August 1998 | |||
11. Mulzer, W., Rote, G.: Minimum-weight triangulation is NP-hard. In: Proceedings 22nd Annual ACM Symposium on Computational Geometry, SoCG'06, Sedona, AZ, USA. ACM Press, New York, NY, USA (2006) | |||
12. Remy, J., Steger, A.: A Quasi-Polynomial Time Approximation Scheme for Minimum Weight Triangulation. In: Proceedings 38th ACM Symposium on Theory of Computing (STOC'06). ACM Press, New York, NY, USA (2006) | |||