Представитель Шуры Люберецкого в ЖЖ (brat_luber) wrote,
Представитель Шуры Люберецкого в ЖЖ
brat_luber

Алгоритмическая задача

Дано: есть матрица высот, то есть (грубо говоря) равномерная сетка точек на поверхности Земли, для каждой из которых приведена ее высота. Точек много, порядка миллиарда. Нужно построить TIN-модель (triangular irregular network), то есть сетку из треугольников с “абы где” расположенными вершинами, “похожую” на исходную матрицу высот. Треугольников должно быть много меньше – несколько десятков тысяч это максимум.

Стандартные алгоритмы построения TIN построены по общему принципу – для каждой точки матрицы высот (всего их N) вычисляется какая-то численная характеристика, связанная с локальными свойствами этой точки, в качестве вершин треугольников выбираются точки с максимальным значением этой характеристики (а их число обозначим M), а затем для построенных вершин строится триангуляция Делоне. Так вот, поговорим про выбор вершин этих треугольников.

В руководстве, откуда я взял это описание, предлагается сначала вычислить характеристику, а уж потом выбрать точки, где она принимает наибольшие значения. Если прикинуть расход памяти для такого действия, то становится очень грустно (не забываем о том, что у нас уже есть загруженная матрица высот). Хочется сделать это несколько более эффективно.

Легко понять, что функция f, выбирающая из последовательности x0, …, xn M максимальных элементов, является индуктивной, то есть f(x0, …, xn) зависит только от f(x0, …, xn-1) и xn. Можно записать это следующим образом: f(x0, …, xn) = F(f(x0, …, xn-1), xn). Индуктивная функция от последовательности длины N вычисляется за N шагов очень простым циклом, надо знать лишь значение f на пустой или одноэлементной последовательности и функцию F.

Очень просто написать функцию, находящую M “наибольших” элементов в N-элементной последовательности за O(N*M) с расходом памяти O(M) – выбранные элементы хранятся в массиве, каждый новый элемент сравнивается со всеми выбранными до этого. Если включить мозг, то можно улучшить оценку до O(N*log M) с той же оценкой расхода памяти (храним выбранные M элементов в самобалансирующемся дереве). А можно ли сделать это еще быстрее, возможно, отказавшись от подхода с индуктивными функциями? Я ответа пока что не знаю.

Запись опубликована в блоге Шуры Люберецкого. Вы можете оставлять свои комментарии там, используя свое имя пользователя из ЖЖ (вход по OpenID).

Tags: программирование
Subscribe

  • О фактчекинге

    Наткнулся на американскую, разумеется, статью “Фактчекинг речи Владимира Путина в ООН”:…

  • Неоламаркизма псто

    Из школьной биологии мы твердо знаем, что приобретенные признаки не наследуются. Кто-то вспомнит про опыт Вейсмана, кто-то задаст простой вопрос…

  • Про псевдонауку

    Пишу сейчас довольно большой и спорный пост, пока не буду раскрывать, о чем – скажу лишь, что залез в википедию (фу, бля – скажете вы и…

Comments for this post were disabled by the author