Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 15.05.2010, 11:25
Новичок

Отправить личное сообщение для cheATGamer Посмотреть профиль Найти все сообщения от cheATGamer
 
Регистрация: 15.05.2010
Сообщений: 2

Реберный путь в многоугольнике по вершинам
Дано многоугольник. Для него можно сделать предобработку.
Подается запрос: 2 точки внутри (или на границе, в вершинах) многоугольника и требуется за O(logN) найти неэвклидовую минимальную длину пути между этими точками по вершинам (т.е нельзя останавливатся посреди многоугольника или его границах, нужно чтобы путь проходил только из одной вершины в другую). Длина пути измеряется просто количеством ребер, а не суммой их длин.

Предположительная сложность предобработки многоугольника O(N^3). Возможно есть и быстрее.

Интересуют любые идеи по этому поводу, решения частичных задач, связанных с данной (например, нахождение видимых вершин из точек запроса за O(logN) и т.п, разбиение многоугольника на области для локализации с каким-то смыслом), а так же литература, которая касалась бы данной задачи. Литература по поискам пути, где путь не обязательно проходит только по вершинам у меня есть, но там ничего полезного для данной задачи я не нашел.

Заранее благодарен.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Путь в Дейкстре misterfix Графы 4 19.12.2009 22:38
Кратчайший путь из А в В siberx Графы 1 11.05.2009 21:25
Элементарый путь, с ограничением по весу и стоимости гость Графы 2 03.05.2009 23:18
Гамильтонов путь минимальной длины гость Графы 5 24.02.2009 01:27
Кратачайший путь (динамическое программирование) Николай Математические алгоритмы 6 06.06.2008 04:34