|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Задача поиска точки, попадающей в полуплоскостьдипломная работа (Специалист)
- Научный руководитель: Гасанов Э.Э.
- Автор: Бабинов Иван Александрович
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2012
- Аннотация: В работе Ивана Бабинова рассматривается следующая задача. Имеется база данных, состоящая из точек плоскости. В качестве запроса поступает произвольная полуплоскость. Необходимо найти хотя бы одну точку из базы, принадлежащую этой полуплоскости, или сказать, что такой точки нет. Получен линейный по памяти алгоритм решения этой задачи с логарифмическим временем поиска. Показано, что в предлагаемую структуру данных может быть добавлена новая точка за линейное от размера данных время. Также рассмотрен случай, когда точки базы данных движутся во времени прямолинейно и равномерно. Введено понятие состояния базы данных, как упорядоченное множество точек на выпуклой оболочке базы данных. С течением времени состояние базы данных меняется. Показано, что любая база данных проходит конечное число состояний, и через какое-то время попадает в финальное состояние, из которого далее не выходит. Получены верхние и нижние оценки на число состояний базы данных, совпадающие по порядку.
- Добавил в систему: Гасанов Эльяр Эльдарович