Верхняя граница MST для точек, лежащих полукругом

Question

Рассмотрим полукруг C с радиусом r на плоскости и набор P из n точек, лежащих на или внутри C. Можем ли мы дать верхнюю оценку стоимости MST для P как функции от r (независимо от n)

Answer 1

Верхняя граница не зависит от n .

Рассмотрим, например, снежинку Коха: https://en.wikipedia.org/wiki/Koch_snowflake

Он вписывается в конечную область, а периметр представляет собой MST, но его длина бесконечна (или приближается к бесконечности, когда вы повторяете конструкцию).

В более общем смысле, вы можете заставить MST следовать любой кривой, которая вам нравится, сколь угодно близко, с помощью выборки кривой с достаточно небольшими приращениями. Поскольку нет ограничений на длину кривой, которую вы можете вложить в область, нет ограничений на стоимость MST, которую вы можете вложить в область.