Самый дальний первый обход

В вычислительной геометрии самый дальний обход компактного метрического пространства представляет собой последовательность точек в пространстве, где первая точка выбирается произвольно, а каждая последующая точка находится как можно дальше от набора ранее выбранных точек. Та же концепция может быть применена к конечному набору геометрических точек, ограничивая выбранные точки принадлежностью к множеству или, что то же самое, рассматривая конечное метрическое пространство, порожденное этими точками. ^[1] Для конечного метрического пространства или конечного набора геометрических точек результирующая последовательность образует перестановку точек, также известную как жадная перестановка . ^[2]

Каждый префикс самого дальнего обхода обеспечивает набор точек, которые широко разнесены и расположены близко ко всем остальным точкам. Точнее, никакой другой набор из одинакового числа точек не может быть расположен более чем в два раза шире, и никакой другой набор из одинакового числа точек не может быть расположен менее чем в два раза дальше от самой дальней оставшейся точки. Частично из-за этих свойств обход самой дальней точки имеет множество приложений, включая аппроксимацию задачи коммивояжера и метрической $задачи k$ -центра . Они могут быть построены за полиномиальное время или (для маломерных евклидовых пространств ) аппроксимированы за почти линейное время .

Определение и свойства

Обход от дальнего конца — это последовательность точек в компактном метрическом пространстве , при этом каждая точка появляется не более одного раза. Если пространство конечно, каждая точка появляется ровно один раз, и обход представляет собой перестановку всех точек в пространстве. Первой точкой последовательности может быть любая точка пространства. Каждая точка $p$ после первой должна иметь максимально возможное расстояние до множества точек, предшествующих $p$ в последовательности, где расстояние от точки до множества определяется как минимальное из попарных расстояний до точек в наборе. В данном пространстве может быть множество различных обходов с самого дальнего конца, в зависимости как от выбора первой точки в последовательности (которая может быть любой точкой в пространстве), так и от связей для максимального расстояния среди последующих вариантов. ^[2]

Обходы самой дальней точки можно охарактеризовать следующими свойствами. Зафиксируйте число $k$ и рассмотрите префикс, образованный первыми $k$ точками самого дальнего первого обхода любого метрического пространства. Пусть $r$ — расстояние между конечной точкой префикса и другими точками префикса. Тогда это подмножество имеет следующие два свойства:

Все пары выбранных точек находятся на расстоянии не менее $r$ друг от друга, а
Все точки метрического пространства находятся на расстоянии не более $r$ от подмножества.

И наоборот, любая последовательность, обладающая этими свойствами, для всех вариантов выбора $k$ должна быть обходом дальше всех. Это два определяющих свойства множества Делоне , поэтому каждый префикс самого дальнего обхода образует множество Делоне. ^[3]

Приложения

Розенкранц, Стернс и Льюис (1977) использовали метод самого дальнего обхода для определения эвристики самого дальнего вставки для задачи коммивояжера . Эта эвристика находит приблизительные решения задачи коммивояжера, строя тур по подмножеству точек, добавляя к туру по одной точке за раз в порядке, заданном самым дальним обходом. Чтобы добавить каждую точку в обход, одно ребро предыдущего обхода разрывается и заменяется парой ребер, проходящих через добавленную точку, самым дешевым способом. Хотя Розенкранц и др. доказать только логарифмический коэффициент аппроксимации для этого метода, они показывают, что на практике он часто работает лучше, чем другие методы вставки с более доказуемыми коэффициентами аппроксимации. ^[4]

Позже та же последовательность точек была популяризирована Гонсалесом (1985) , который использовал ее как часть жадных алгоритмов аппроксимации для двух задач кластеризации, целью которых является разделение набора точек на $k$ кластеров. Одна из двух задач, которые Гонсалес решает таким образом, стремится минимизировать максимальный диаметр кластера, в то время как другая, известная как метрическая $проблема k$ -центра , стремится минимизировать максимальный радиус, расстояние от выбранной центральной точки кластера. кластера в самую дальнюю от него точку в том же кластере. Например, $задачу k$ -центра можно использовать для моделирования размещения пожарных частей в городе, чтобы гарантировать, что пожарная машина может быстро добраться до каждого адреса в городе. Для обеих задач кластеризации Гонсалес выбирает набор из $k$ центров кластеров, выбирая первые $k$ точек самого дальнего обхода, а затем создает кластеры, присваивая каждую входную точку ближайшему центру кластера. Если $r$ - расстояние от набора из $k$ выбранных центров до следующей точки в позиции $k + 1$ при обходе, то при такой кластеризации каждая точка находится на расстоянии $r$ от своего центра, и каждый кластер имеет диаметр не более $2 r$ . Однако все подмножество $k$ центров вместе со следующей точкой находятся на расстоянии не менее $r$ друг от друга, и любая $k$ -кластеризация поместила бы некоторые две из этих точек в один кластер, причем одна из них находится на расстоянии не менее $r / 2$ от его центра и диаметром не менее $r$ . Таким образом, эвристика Гонсалеса дает коэффициент аппроксимации 2 для обеих задач кластеризации. ^[3]

Эвристика Гонсалеса была независимо переоткрыта для метрической $k$ проблемы -центра Дайером и Фризом (1985) , которые применили ее в более общем плане к задачам с взвешенными $k$ -центрами. ^[5] В другой статье $k$ того же времени по проблеме -центра, Хохбаум и Шмойс (1985) , достигнут тот же коэффициент аппроксимации, равный 2: ^[6] но его методы разные. ^[5] Тем не менее, эвристика Гонсалеса и название «самый дальний обход» часто ошибочно приписывают Хохбауму и Шмойсу. ^[7] Как для задачи кластеризации минимального-максимального диаметра, так и для метрической $задачи k$ -центра эти аппроксимации оптимальны: существование эвристики с полиномиальным временем с любым постоянным коэффициентом аппроксимации меньше 2 будет означать, что P = NP . ^[3]^[6]

Помимо кластеризации, обход по принципу «самый дальний — первый» может также использоваться в задаче размещения объектов другого типа — задаче максим-минимной дисперсии объектов, в которой цель состоит в том, чтобы выбрать расположение $k$ различных объектов так, чтобы они находились как можно дальше друг от друга. как можно дальше друг от друга. Точнее, цель этой задачи — выбрать $k$ точек из заданного метрического пространства или заданного набора точек-кандидатов таким образом, чтобы максимизировать минимальное попарное расстояние между выбранными точками. Опять же, это можно аппроксимировать, выбрав первые $k$ точек самого дальнего первого обхода. Если $r$ обозначает расстояние $k$ -й точки от всех предыдущих точек, то каждая точка метрического пространства или набора кандидатов находится на расстоянии $r$ от первых $k - 1$ точек. По принципу «ячейки» некоторые две точки оптимального решения (каким бы оно ни было) должны находиться на расстоянии $r$ от одной и той же точки среди этих первых $k - 1$ выбранных точек и (согласно неравенству треугольника ) на расстоянии $2 r$ друг от друга . . Следовательно, эвристическое решение, полученное в результате самого дальнего обхода, находится в пределах двух от оптимального. ^[8]^[9]^[10]

Другие применения метода дальнего обхода включают квантование цвета (группирование цветов изображения в меньший набор репрезентативных цветов), ^[11] прогрессивное сканирование изображений (выбор порядка отображения пикселей изображения, чтобы префиксы порядка создавали хорошие версии всего изображения с более низким разрешением, а не заполняли изображение сверху вниз), ^[12]выбор точки в вероятностном методе дорожной карты для планирования движения , ^[13] упрощение облаков точек , ^[14] создание масок для полутоновых изображений, ^[15]^[16] иерархическая кластеризация , ^[1] поиск сходства между полигональными сетками похожих поверхностей, ^[17] выбор разнообразных и ценных объектов наблюдения для исследования подводных роботов, ^[18] обнаружение неисправностей в сенсорных сетях , ^[19] моделирование филогенетического разнообразия , ^[20] подбор транспортных средств из разнородного парка в соответствии с запросами клиентов на доставку, ^[21] равномерное распределение геодезических обсерваторий на поверхности Земли ^[22] или других типов сенсорной сети, ^[23] генерация виртуальных точечных источников света в методе рендеринга компьютерной графики мгновенного излучения , ^[24] и поиска геометрического диапазона структуры данных . ^[25]

Алгоритмы

Жадный точный алгоритм

Самый дальний обход конечного набора точек может быть вычислен с помощью жадного алгоритма , который поддерживает расстояние каждой точки от ранее выбранных точек, выполняя следующие шаги: ^[3]

Инициализируйте последовательность выбранных точек пустой последовательностью, а расстояния каждой точки до выбранных точек - до бесконечности.
Пока не все точки выбраны, повторите следующие действия:
- Просканируйте список еще не выбранных точек, чтобы найти точку $p$ , которая находится на максимальном расстоянии от выбранных точек.
- Удалите $p$ из еще не выбранных точек и добавьте его в конец последовательности выбранных точек.
- Для каждой оставшейся еще не выбранной точки $q$ замените расстояние, сохраненное для $q,$ на минимум ее старого значения и расстояние от $p$ до $q$ .

Для набора из $n$ точек этот алгоритм принимает $O (n 2)$ шагов и $O (n 2)$ расчеты расстояний. ^[3]

Приближения

Более быстрый алгоритм аппроксимации , предложенный Хар-Пеледом и Менделем (2006) , применяется к любому подмножеству точек в метрическом пространстве с ограниченной удвоенной размерностью , классе пространств, которые включают евклидовы пространства ограниченной размерности. Их алгоритм находит последовательность точек, в которой каждая последующая точка имеет расстояние в пределах $1 - ε$ фактора самого дальнего расстояния от ранее выбранной точки, где $ε$ может быть выбрано в качестве любого положительного числа. Это требует времени $O(n\log n)$ . ^[2]

Результаты для ограниченной удвоенной размерности не применимы к многомерным евклидовым пространствам, поскольку постоянный множитель в обозначении большого О для этих алгоритмов зависит от размерности. Вместо этого другой метод аппроксимации, основанный на лемме Джонсона – Линденштрауса и локально-чувствительном хешировании, имеет время выполнения. $O(\varepsilon ^{-2}n^{1+1/(1+\varepsilon )^{2}+o(1)}).$ Для метрик, определяемых кратчайшими путями на взвешенных неориентированных графах, рандомизированная инкрементная конструкция, основанная на алгоритме Дейкстры, позволяет достичь времени $O(\varepsilon ^{-1}m\log n\log {\tfrac {n}{\varepsilon }})$ , где $n$ и $m$ — количество вершин и ребер входного графа соответственно. ^[26]

Инкрементная вставка Вороного

Для выбора точек из непрерывного пространства, такого как евклидова плоскость , а не из конечного набора точек-кандидатов, эти методы не будут работать напрямую, поскольку потребуется поддерживать бесконечное количество расстояний. Вместо этого каждая новая точка должна выбираться как центр наибольшего пустого круга, определенного ранее выбранным набором точек. ^[12] Этот центр всегда будет лежать в вершине диаграммы Вороного уже выбранных точек или в точке, где ребро диаграммы Вороного пересекает границу области. В этой формулировке метод построения дальнего обхода также называется инкрементальной вставкой Вороного . ^[27] Оно похоже на уточнение Делоне для конечных элементов генерации сетки , но отличается выбором, какую вершину Вороного вставлять на каждом шаге. ^[28]

См. также

Алгоритм Ллойда , другой метод создания равномерно расположенных точек в геометрических пространствах.

Ссылки

^ Перейти обратно: ^а ^б Дасгупта, С.; Лонг, П.М. (2005), «Гарантии производительности для иерархической кластеризации», Журнал компьютерных и системных наук , 70 (4): 555–569, doi : 10.1016/j.jcss.2004.10.006 , MR 2136964
^ Перейти обратно: ^а ^б ^с Хар-Пелед, С. ; Мендель, М. (2006), «Быстрое построение сетей в низкоразмерных метриках и их приложения», SIAM Journal on Computing , 35 (5): 1148–1184, arXiv : cs/0409057 , doi : 10.1137/S0097539704446281 , МР 2217141 , S2CID 37346335
^ Перейти обратно: ^а ^б ^с ^д ^и Гонсалес, Т.Ф. (1985), «Кластеризация для минимизации максимального расстояния между кластерами», Theoretical Computer Science , 38 (2–3): 293–306, doi : 10.1016/0304-3975(85)90224-5 , MR 0807927
^ Розенкранц, диджей; Стернс, RE; Льюис, PM II (1977), «Анализ нескольких эвристик для задачи коммивояжера», SIAM Journal on Computing , 6 (3): 563–581, doi : 10.1137/0206041 , MR 0459617 , S2CID 14764079
^ Перейти обратно: ^а ^б Дайер, Мэн ; Фриз, AM (1985), «Простая эвристика для $проблемы p$ -центра» (PDF) , Operations Research Letters , 3 (6): 285–288, doi : 10.1016/0167-6377(85)90002-1 , MR 0797340
^ Перейти обратно: ^а ^б Хохбаум, Дорит С .; Шмойс, Дэвид Б. (1985), «Наилучшая эвристика для $проблемы k$ -центра», Mathematics of Operations Research , 10 (2): 180–184, doi : 10.1287/moor.10.2.180 , MR 0793876
^
Яркие примеры неправильного приписывания самой дальней эвристики Хохбауму и Шмойсу (1985) см., например,
- Дасгупта, Санджой (2002), «Гарантии производительности для иерархической кластеризации», Кивинен, Юрки; Слоан, Роберт Х. (ред.), Теория вычислительного обучения, 15-я ежегодная конференция по теории вычислительного обучения, COLT 2002, Сидней, Австралия, 8–10 июля 2002 г., Труды , Конспекты лекций по информатике, том. 2375, Springer, стр. 351–363, номер документа : 10.1007/3-540-45435-7_24 , ISBN. 978-3-540-43836-6 (исправлено в журнальной версии той же статьи за 2005 г.)
- Агарвал, Самир; Рамамурти, Рави; Белонги, Серж Дж.; Йенсен, Хенрик Ванн (2003), «Структурированная выборка по важности карт окружающей среды», ACM Trans. График. , 22 (3): 605–612, дои : 10.1145/882262.882314
- Барам, Йорам; Эль-Янив, Ран; Луз, Коби (2004), «Онлайн-выбор алгоритмов активного обучения» (PDF) , Дж. Мах. Учиться. Рез. , 5 : 255–291
- Басу, Сугато; Биленко Михаил; Банерджи, Ариндам; Муни, Раймонд Дж. (2006), «Вероятностная полуконтролируемая кластеризация с ограничениями», в Шапель, Оливье; Шёлкопф, Бернхард; Зиен, Александр (ред.), Обучение с полуконтролем , MIT Press, стр. 73–102, doi : 10.7551/mitpress/9780262033589.003.0005 , ISBN 978-0-262-03358-9
- Лима, Кристиана Феррейра Лемос; Ассис, Франциско М.; де Соуза, Клеонилсон Протасио (2011), «Сравнительное исследование использования энтропии Шеннона, Реньи и Тсаллиса для выбора атрибутов при обнаружении сетевых вторжений», Международный семинар IEEE по измерениям и сетям, M&N 2011, Анакапри, Италия, 10-11 октября , 2011 , IEEE, стр. 77–82, номер документа : 10.1109/IWMN.2011.6088496 , S2CID 7510040.
- «Class FarthestFirst» , Weka , версия 3.9.5 , Университет Вайкато, 21 декабря 2020 г. , получено 6 ноября 2021 г. - через SourceForge.
^ Уайт, Дуглас Дж. (1991), «Проблема максимальной дисперсии», Журнал IMA по математике, прикладной в бизнесе и промышленности , 3 (2): 131–140 (1992), doi : 10.1093/imaman/3.2.131 , MR 1154657 ; Уайт считает, что использование самого дальнего обхода в качестве эвристики для решения этой проблемы Стойер, Р.Э. (1986), Многокритериальная оптимизация: теория, вычисления и приложения , Нью-Йорк: Wiley.
^ Тамир, Ари (1991), «Неприятное расположение объектов на графиках», SIAM Journal on Discrete Mathematics , 4 (4): 550–567, doi : 10.1137/0404048 , MR 1129392
^ Рави, СС; Розенкранц, диджей; Тайи, Г.К. (1994), «Эвристические и специальные алгоритмы для задач дисперсии», Operations Research , 42 (2): 299–310, doi : 10.1287/opre.42.2.299 , JSTOR 171673 , S2CID 16489402
^ Сян, З. (1997), «Квантование цветного изображения путем минимизации максимального расстояния между кластерами», ACM Transactions on Graphics , 16 (3): 260–276, doi : 10.1145/256157.256159 , S2CID 17713417
^ Перейти обратно: ^а ^б Эльдар, Ю.; Линденбаум, М.; Порат, М.; Зееви, YY (1997), «Стратегия самой дальней точки для прогрессивной выборки изображений», IEEE Transactions on Image Processing , 6 (9): 1305–1315, Bibcode : 1997ITIP....6.1305E , doi : 10.1109/83.623193 , PMID 18283019
^ Мазер, Э.; Ауактцин, Дж. М.; Бессьер, П. (1998), «Алгоритм клубка Ариадны», Журнал исследований искусственного интеллекта , 9 : 295–316, arXiv : 1105.5440 , doi : 10.1613/jair.468
^ Мённинг, К.; Доджсон, Н.А. (2003), «Новый алгоритм упрощения облака точек», 3-я Международная конференция IASTED по визуализации, визуализации и обработке изображений.
^ Гоцман, Крейг; Аллебах, Ян П. (1996), «Границы и алгоритмы для экранов с дизерингом» (PDF) , в Роговитце, Бернис Э.; Аллебах, Ян П. (ред.), Человеческое зрение и электронная визуализация , Proc. СПИЭ, том. 2657, стр. 483–492, doi : 10.1117/12.238746 , S2CID 10608234.
^ Шахиди, Р.; Молони, К.; Рампони, Г. (2004), «Проектирование масок самой дальней точки для растрового изображения», Журнал EURASIP по прикладной обработке сигналов , 2004 (12): 1886–1898, Бибкод : 2004EJASP2004...45S , doi : 10.1155/S1110865704403217
^ Липман, Ю.; Фанкхаузер, Т. (2009), «Голосование Мёбиуса за поверхностную корреспонденцию», Proc. ACM SIGGRAPH , стр. 72:1–72:12, doi : 10.1145/1576246.1531378 , ISBN 978-1-60558-726-4 , S2CID 6001942
^ Гирдхар, Ю.; Жигер, П.; Дудек, Г. (2012), «Автономные адаптивные подводные исследования с использованием тематического онлайн-моделирования» (PDF) , Proc. Межд. Симп. Экспериментальная робототехника
^ Алтинисик, У.; Йылдирим, М.; Эркан, К. (2012), «Изолирование непредопределенных неисправностей датчика с помощью алгоритма самого дальнего первого обхода», Индиана, Инженер. хим. Рез. , 51 (32): 10641–10648, doi : 10.1021/ie201850k
^ Бордевич, Магнус; Родриго, Аллен; Семпл, Чарльз (2008), «Выбор таксонов для сохранения или секвенирования: желательные критерии и жадное решение», Systematic Biology , 57 (6): 825–834, doi : 10.1080/10635150802552831 , PMID 19085326
^ Фишер, Маршалл Л.; Джайкумар, Рамчандран (1981), «Эвристика обобщенного назначения для маршрутизации транспортных средств», Networks , 11 (2): 109–124, doi : 10.1002/net.3230110205 , MR 0618209 ; как цитирует Гейсенс, Филип; Голден, Брюс; Асад, Арджанг (1986), «Новая эвристика для определения размера и состава флота», в Галло, Джорджио; Сэнди, Клаудио (ред.), Netflow в Пизе , Исследования по математическому программированию, том. 26, Спрингер, стр. 233–236, номер документа : 10.1007/bfb0121103 , ISBN. 978-3-642-00922-8
^ Хасэ, Хайо (2000), «Новый метод выбора дополнительных мест для гомогенизации неоднородного распределения косферических точек», Раммель, Рейнхард; Древес, Герман; Босх, Вольфганг; и др. (ред.), На пути к интегрированной глобальной системе геодезических наблюдений (IGGOS): Симпозиум II секции IAG, Мюнхен, 5-9 октября 1998 г., Плакаты - Сессия B , Симпозиумы Международной ассоциации геодезии, том. 120, Springer, стр. 180–183, номер документа : 10.1007/978-3-642-59745-9_35 , ISBN. 978-3-642-64107-7
^ Виейра, Луис Филипе М.; Виейра, Маркос Аугусто М.; Руис, Линьер Беатрис ; Лоурейро, Антонио А.Ф.; Сильва, Диоген Сесилио; Фернандес, Антонио Отавио (2004), «Эффективный алгоритм развертывания дополнительной сенсорной сети» (PDF) , Proc. Бразильский симп. Компьютерные сети , стр. 3–14
^ Лайне, Самули; Сарансаари, Ханну; Контканен, Янне; Лехтинен, Яакко; Айла, Тимо (2007), «Постепенная мгновенная излучательность для непрямого освещения в реальном времени», Материалы 18-й конференции Eurographics по методам рендеринга (EGSR'07) , Эйр-ла-Виль, Швейцария, Швейцария: Ассоциация Eurographics, стр. 277–286, номер домена : 10.2312/EGWR/EGSR07/277-286 , ISBN 978-3-905673-52-4 , S2CID 18626929
^ Аббар, С.; Амер-Яхия, С.; Индик, П. ; Махабади, С.; Варадараджан, КР (2013), «Разнообразная проблема ближнего соседа», Труды 29-го ежегодного симпозиума по вычислительной геометрии , стр. 207–214, doi : 10.1145/2462356.2462401 , hdl : 1721.1/87000 , ISBN 978-1-4503-2031-3 , S2CID 6286186
^ Эппштейн, Дэвид ; Хар-Пелед, Сариэль ; Сидиропулос, Анастасиос (2020), «Приблизительная жадная кластеризация и дистанционный выбор для метрик графа», Journal of Computational Geometry , 11 (1): 629–652, doi : 10.20382/jocg.v11i1a25 , MR 4194877 , S2CID 18316279
^ Терамото, Сачио; Асано, Тецуо ; Като, Наоки; Дорр, Бенджамин (2006), «Вставка точек единообразно в каждом экземпляре» , Транзакции IEICE по информации и системам , E89-D (8): 2348–2356, Bibcode : 2006IEITI..89.2348T , doi : 10.1093/ietisy/e89- д.8.2348 , лдл : 2433/84849
^ Руперт, Джим (1995), «Алгоритм уточнения Делоне для создания качественной двумерной сетки», Journal of Algorithms , 18 (3): 548–585, doi : 10.1006/jagm.1995.1021

[daslon-1] Перейти обратно: ^а ^б Дасгупта, С.; Лонг, П.М. (2005), «Гарантии производительности для иерархической кластеризации», Журнал компьютерных и системных наук , 70 (4): 555–569, doi : 10.1016/j.jcss.2004.10.006 , MR 2136964

[harmen-2] Перейти обратно: ^а ^б ^с Хар-Пелед, С. ; Мендель, М. (2006), «Быстрое построение сетей в низкоразмерных метриках и их приложения», SIAM Journal on Computing , 35 (5): 1148–1184, arXiv : cs/0409057 , doi : 10.1137/S0097539704446281 , МР 2217141 , S2CID 37346335

[gonzalez-3] Перейти обратно: ^а ^б ^с ^д ^и Гонсалес, Т.Ф. (1985), «Кластеризация для минимизации максимального расстояния между кластерами», Theoretical Computer Science , 38 (2–3): 293–306, doi : 10.1016/0304-3975(85)90224-5 , MR 0807927

[rosste-4] Розенкранц, диджей; Стернс, RE; Льюис, PM II (1977), «Анализ нескольких эвристик для задачи коммивояжера», SIAM Journal on Computing , 6 (3): 563–581, doi : 10.1137/0206041 , MR 0459617 , S2CID 14764079

[dyfr-5] Перейти обратно: ^а ^б Дайер, Мэн ; Фриз, AM (1985), «Простая эвристика для $проблемы p$ -центра» (PDF) , Operations Research Letters , 3 (6): 285–288, doi : 10.1016/0167-6377(85)90002-1 , MR 0797340

[hocshm-6] Перейти обратно: ^а ^б Хохбаум, Дорит С .; Шмойс, Дэвид Б. (1985), «Наилучшая эвристика для $проблемы k$ -центра», Mathematics of Operations Research , 10 (2): 180–184, doi : 10.1287/moor.10.2.180 , MR 0793876

[incorrect-7] Яркие примеры неправильного приписывания самой дальней эвристики Хохбауму и Шмойсу (1985) см., например,
Дасгупта, Санджой (2002), «Гарантии производительности для иерархической кластеризации», Кивинен, Юрки; Слоан, Роберт Х. (ред.), Теория вычислительного обучения, 15-я ежегодная конференция по теории вычислительного обучения, COLT 2002, Сидней, Австралия, 8–10 июля 2002 г., Труды , Конспекты лекций по информатике, том. 2375, Springer, стр. 351–363, номер документа : 10.1007/3-540-45435-7_24 , ISBN. 978-3-540-43836-6 (исправлено в журнальной версии той же статьи за 2005 г.)
Агарвал, Самир; Рамамурти, Рави; Белонги, Серж Дж.; Йенсен, Хенрик Ванн (2003), «Структурированная выборка по важности карт окружающей среды», ACM Trans. График. , 22 (3): 605–612, дои : 10.1145/882262.882314
Барам, Йорам; Эль-Янив, Ран; Луз, Коби (2004), «Онлайн-выбор алгоритмов активного обучения» (PDF) , Дж. Мах. Учиться. Рез. , 5 : 255–291
Басу, Сугато; Биленко Михаил; Банерджи, Ариндам; Муни, Раймонд Дж. (2006), «Вероятностная полуконтролируемая кластеризация с ограничениями», в Шапель, Оливье; Шёлкопф, Бернхард; Зиен, Александр (ред.), Обучение с полуконтролем , MIT Press, стр. 73–102, doi : 10.7551/mitpress/9780262033589.003.0005 , ISBN 978-0-262-03358-9
Лима, Кристиана Феррейра Лемос; Ассис, Франциско М.; де Соуза, Клеонилсон Протасио (2011), «Сравнительное исследование использования энтропии Шеннона, Реньи и Тсаллиса для выбора атрибутов при обнаружении сетевых вторжений», Международный семинар IEEE по измерениям и сетям, M&N 2011, Анакапри, Италия, 10-11 октября , 2011 , IEEE, стр. 77–82, номер документа : 10.1109/IWMN.2011.6088496 , S2CID 7510040.
«Class FarthestFirst» , Weka , версия 3.9.5 , Университет Вайкато, 21 декабря 2020 г. , получено 6 ноября 2021 г. - через SourceForge.

[8] Дасгупта, Санджой (2002), «Гарантии производительности для иерархической кластеризации», Кивинен, Юрки; Слоан, Роберт Х. (ред.), Теория вычислительного обучения, 15-я ежегодная конференция по теории вычислительного обучения, COLT 2002, Сидней, Австралия, 8–10 июля 2002 г., Труды , Конспекты лекций по информатике, том. 2375, Springer, стр. 351–363, номер документа : 10.1007/3-540-45435-7_24 , ISBN. 978-3-540-43836-6 (исправлено в журнальной версии той же статьи за 2005 г.)

[9] Агарвал, Самир; Рамамурти, Рави; Белонги, Серж Дж.; Йенсен, Хенрик Ванн (2003), «Структурированная выборка по важности карт окружающей среды», ACM Trans. График. , 22 (3): 605–612, дои : 10.1145/882262.882314

[10] Барам, Йорам; Эль-Янив, Ран; Луз, Коби (2004), «Онлайн-выбор алгоритмов активного обучения» (PDF) , Дж. Мах. Учиться. Рез. , 5 : 255–291

[11] Басу, Сугато; Биленко Михаил; Банерджи, Ариндам; Муни, Раймонд Дж. (2006), «Вероятностная полуконтролируемая кластеризация с ограничениями», в Шапель, Оливье; Шёлкопф, Бернхард; Зиен, Александр (ред.), Обучение с полуконтролем , MIT Press, стр. 73–102, doi : 10.7551/mitpress/9780262033589.003.0005 , ISBN 978-0-262-03358-9

[12] Лима, Кристиана Феррейра Лемос; Ассис, Франциско М.; де Соуза, Клеонилсон Протасио (2011), «Сравнительное исследование использования энтропии Шеннона, Реньи и Тсаллиса для выбора атрибутов при обнаружении сетевых вторжений», Международный семинар IEEE по измерениям и сетям, M&N 2011, Анакапри, Италия, 10-11 октября , 2011 , IEEE, стр. 77–82, номер документа : 10.1109/IWMN.2011.6088496 , S2CID 7510040.

[13] «Class FarthestFirst» , Weka , версия 3.9.5 , Университет Вайкато, 21 декабря 2020 г. , получено 6 ноября 2021 г. - через SourceForge.

[white-8] Уайт, Дуглас Дж. (1991), «Проблема максимальной дисперсии», Журнал IMA по математике, прикладной в бизнесе и промышленности , 3 (2): 131–140 (1992), doi : 10.1093/imaman/3.2.131 , MR 1154657 ; Уайт считает, что использование самого дальнего обхода в качестве эвристики для решения этой проблемы Стойер, Р.Э. (1986), Многокритериальная оптимизация: теория, вычисления и приложения , Нью-Йорк: Wiley.

[tamir-9] Тамир, Ари (1991), «Неприятное расположение объектов на графиках», SIAM Journal on Discrete Mathematics , 4 (4): 550–567, doi : 10.1137/0404048 , MR 1129392

[ravros-10] Рави, СС; Розенкранц, диджей; Тайи, Г.К. (1994), «Эвристические и специальные алгоритмы для задач дисперсии», Operations Research , 42 (2): 299–310, doi : 10.1287/opre.42.2.299 , JSTOR 171673 , S2CID 16489402

[xiang-11] Сян, З. (1997), «Квантование цветного изображения путем минимизации максимального расстояния между кластерами», ACM Transactions on Graphics , 16 (3): 260–276, doi : 10.1145/256157.256159 , S2CID 17713417

[elpz-12] Перейти обратно: ^а ^б Эльдар, Ю.; Линденбаум, М.; Порат, М.; Зееви, YY (1997), «Стратегия самой дальней точки для прогрессивной выборки изображений», IEEE Transactions on Image Processing , 6 (9): 1305–1315, Bibcode : 1997ITIP....6.1305E , doi : 10.1109/83.623193 , PMID 18283019

[mab-13] Мазер, Э.; Ауактцин, Дж. М.; Бессьер, П. (1998), «Алгоритм клубка Ариадны», Журнал исследований искусственного интеллекта , 9 : 295–316, arXiv : 1105.5440 , doi : 10.1613/jair.468

[moedod-14] Мённинг, К.; Доджсон, Н.А. (2003), «Новый алгоритм упрощения облака точек», 3-я Международная конференция IASTED по визуализации, визуализации и обработке изображений.

[gotall-15] Гоцман, Крейг; Аллебах, Ян П. (1996), «Границы и алгоритмы для экранов с дизерингом» (PDF) , в Роговитце, Бернис Э.; Аллебах, Ян П. (ред.), Человеческое зрение и электронная визуализация , Proc. СПИЭ, том. 2657, стр. 483–492, doi : 10.1117/12.238746 , S2CID 10608234.

[shamol-16] Шахиди, Р.; Молони, К.; Рампони, Г. (2004), «Проектирование масок самой дальней точки для растрового изображения», Журнал EURASIP по прикладной обработке сигналов , 2004 (12): 1886–1898, Бибкод : 2004EJASP2004...45S , doi : 10.1155/S1110865704403217

[lipfun-17] Липман, Ю.; Фанкхаузер, Т. (2009), «Голосование Мёбиуса за поверхностную корреспонденцию», Proc. ACM SIGGRAPH , стр. 72:1–72:12, doi : 10.1145/1576246.1531378 , ISBN 978-1-60558-726-4 , S2CID 6001942

[ggd-18] Гирдхар, Ю.; Жигер, П.; Дудек, Г. (2012), «Автономные адаптивные подводные исследования с использованием тематического онлайн-моделирования» (PDF) , Proc. Межд. Симп. Экспериментальная робототехника

[aye-19] Алтинисик, У.; Йылдирим, М.; Эркан, К. (2012), «Изолирование непредопределенных неисправностей датчика с помощью алгоритма самого дальнего первого обхода», Индиана, Инженер. хим. Рез. , 51 (32): 10641–10648, doi : 10.1021/ie201850k

[borrod-20] Бордевич, Магнус; Родриго, Аллен; Семпл, Чарльз (2008), «Выбор таксонов для сохранения или секвенирования: желательные критерии и жадное решение», Systematic Biology , 57 (6): 825–834, doi : 10.1080/10635150802552831 , PMID 19085326

[fisjai-21] Фишер, Маршалл Л.; Джайкумар, Рамчандран (1981), «Эвристика обобщенного назначения для маршрутизации транспортных средств», Networks , 11 (2): 109–124, doi : 10.1002/net.3230110205 , MR 0618209 ; как цитирует Гейсенс, Филип; Голден, Брюс; Асад, Арджанг (1986), «Новая эвристика для определения размера и состава флота», в Галло, Джорджио; Сэнди, Клаудио (ред.), Netflow в Пизе , Исследования по математическому программированию, том. 26, Спрингер, стр. 233–236, номер документа : 10.1007/bfb0121103 , ISBN. 978-3-642-00922-8

[hase-22] Хасэ, Хайо (2000), «Новый метод выбора дополнительных мест для гомогенизации неоднородного распределения косферических точек», Раммель, Рейнхард; Древес, Герман; Босх, Вольфганг; и др. (ред.), На пути к интегрированной глобальной системе геодезических наблюдений (IGGOS): Симпозиум II секции IAG, Мюнхен, 5-9 октября 1998 г., Плакаты - Сессия B , Симпозиумы Международной ассоциации геодезии, том. 120, Springer, стр. 180–183, номер документа : 10.1007/978-3-642-59745-9_35 , ISBN. 978-3-642-64107-7

[vievie-23] Виейра, Луис Филипе М.; Виейра, Маркос Аугусто М.; Руис, Линьер Беатрис ; Лоурейро, Антонио А.Ф.; Сильва, Диоген Сесилио; Фернандес, Антонио Отавио (2004), «Эффективный алгоритм развертывания дополнительной сенсорной сети» (PDF) , Proc. Бразильский симп. Компьютерные сети , стр. 3–14

[laisar-24] Лайне, Самули; Сарансаари, Ханну; Контканен, Янне; Лехтинен, Яакко; Айла, Тимо (2007), «Постепенная мгновенная излучательность для непрямого освещения в реальном времени», Материалы 18-й конференции Eurographics по методам рендеринга (EGSR'07) , Эйр-ла-Виль, Швейцария, Швейцария: Ассоциация Eurographics, стр. 277–286, номер домена : 10.2312/EGWR/EGSR07/277-286 , ISBN 978-3-905673-52-4 , S2CID 18626929

[abbame-25] Аббар, С.; Амер-Яхия, С.; Индик, П. ; Махабади, С.; Варадараджан, КР (2013), «Разнообразная проблема ближнего соседа», Труды 29-го ежегодного симпозиума по вычислительной геометрии , стр. 207–214, doi : 10.1145/2462356.2462401 , hdl : 1721.1/87000 , ISBN 978-1-4503-2031-3 , S2CID 6286186

[ehs-26] Эппштейн, Дэвид ; Хар-Пелед, Сариэль ; Сидиропулос, Анастасиос (2020), «Приблизительная жадная кластеризация и дистанционный выбор для метрик графа», Journal of Computational Geometry , 11 (1): 629–652, doi : 10.20382/jocg.v11i1a25 , MR 4194877 , S2CID 18316279

[terasa-27] Терамото, Сачио; Асано, Тецуо ; Като, Наоки; Дорр, Бенджамин (2006), «Вставка точек единообразно в каждом экземпляре» , Транзакции IEICE по информации и системам , E89-D (8): 2348–2356, Bibcode : 2006IEITI..89.2348T , doi : 10.1093/ietisy/e89- д.8.2348 , лдл : 2433/84849

[ruppert-28] Руперт, Джим (1995), «Алгоритм уточнения Делоне для создания качественной двумерной сетки», Journal of Algorithms , 18 (3): 548–585, doi : 10.1006/jagm.1995.1021

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]