Операция выполнена!
Закрыть
info@vsetut.pro
О проекте
Вернуться
Об одном интересном свойстве триангуляции Делоне
13.07.2024 10:45:32 | Хабр
Хабы: Алгоритмы, Математика, Спортивное программирование, Занимательные задачки

В процессе решения некоторой задачи, я наткнулся на одно интересное свойство триангуляции Делоне, которое мне не удалось загуглить, как и его применение к решению разных задач. Я уверен, что не являюсь его первооткрывателем, но оно, по крайней мере, не является широко известным. Поэтому я решил написать о нем статью.

Свойство: Если какой-то отрезок AB не включен в триангуляцию Делоне, то существует путь из A в B по отрезкам из триангуляции, такой что все отрезки там не длиннее |AB|. На картинке выше отсутствующий отрезок показан красным цветом, а путь - зеленым цветом.

Дальше в статье я приведу пример его использования в задачах, а также формальное его доказательство.

Если вам известно более красивое доказательство этого свойства, или вы его где-то видели - поделитесь, пожалуйста, в комментариях. Также буду благодарен, если вы поделитесь другими решениями для приведенных в статье задач или аналогичными задачами.

Читать далее
Подробнее
Читайте также
НОВОСТИ

ВСЕ НОВОСТИ
ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro

Copyright © 2024 - vsetut.pro