Теорема о бутерброде с ветчиной
-
Теорема сэндвича с ветчиной
- Утверждает, что в n-мерном евклидовом пространстве можно разделить n объектов пополам с помощью одномерной гиперплоскости.
- Объекты могут перекрываться.
- Предложена Хьюго Штайнхаусом и доказана Стефаном Банахом.
-
История и названия
- Названа в честь случая n = 3, где объекты являются ингредиентами бутерброда с ветчиной.
- В двух измерениях известна как теорема о блинах.
- В 1942 году доказана Стоуном и Тьюки, названа теоремой Стоуна–Тьюки.
-
Двумерный вариант
- Доказан с помощью вращающегося ножа.
- Для каждого угла α можно разрезать блин №1 пополам.
- Для блина №2 можно найти угол, при котором доля блина с положительной стороны ножа равна 1/2.
-
n-мерный вариант
- Доказан с использованием теоремы Борсука–Улама.
- Для каждой точки на сфере S можно найти гиперплоскость, делящую объекты пополам.
- Функция f из (n − 1)-сферы в (n − 1)-мерное пространство показывает, что объемы объектов одинаковы с положительной и отрицательной стороны гиперплоскости.
-
Версии, основанные на теории измерений
- Стоун и Тьюки доказали две версии теоремы для множеств с каратеодорической внешней мерой.
- Первая версия обобщает стандартную теорему, позволяя f(s, x) = s1x1 + … + snxn.
- Вторая версия обобщает стандартную теорему, допуская, что f0 (x) = 1, а fi(x) при i > 0 является i-й координатой x.
-
Варианты дискретной и вычислительной геометрии
- В дискретной геометрии теорема относится к конечному множеству точек.
- В вычислительной геометрии задача о сэндвиче с ветчиной приводит к алгоритмам для нахождения оптимального решения.
- Мегиддо (1985) предложил алгоритм для особого случая.
- Эдельсбруннер и Ваупотич (1986) предложили алгоритм для общего случая.
- Ло и Стайгер (1990) нашли оптимальный алгоритм, работающий за O(n) время.
-
Алгоритм Lo, Matoušek & Steiger
- Расширен до более высоких значений Lo, Matoušek & Steiger (1994)
- Время выполнения составляет o(n^d-1)
- Вычисляет (d-1)-мерную гиперплоскость, разделяющую точки в d-мерном пространстве
-
Обобщения
- Исходная теорема работает для n коллекций
- Для большего числа коллекций можно использовать алгебраическую поверхность степени k
- Доказательство основано на преобразовании n-мерной плоскости в (k+n-1)-мерную плоскость
-
Пример
- Для n = 2 и k = 2 двумерная плоскость отображается на 5-мерную плоскость
-
Рекомендации
- Смотрите также точное разделение
- Рекомендации по цитированию и оформлению