Использование ближайшей и самой дальней пары точек

Question

Не могли бы вы представить себе какие-либо применения ближайшей пары точек и самой дальней пары точек в любом измерении и любой метрике?

Вот мои идеи.

Ближайшим пара точек:

• тестирование - у нас есть множество точек, которые являются, например, некоторые лаборатории, принадлежащие какой-либо компании; компания построила телепорт; он может быть восстановлен только в этих лабораториях, поскольку, например, их стены были построены с золотом, и необходимо, чтобы телепорт был инкапсулирован в золотой комнате по какой-то причине; но телепортер производит магнитное поле, и если они построят 2 телепортатора на одном факультете, поля будут вмешиваться, и они не будут работать; и из них они хотят протестировать их, и было бы хорошо сначала проверить их на как можно меньшем расстоянии; поэтому они должны найти две лаборатории, которые находятся ближе друг к другу
• много путешествий - пункты больницы; каждая больница имеет ровно 1 кг пенициллина (или любого лекарства); Г-ну Х требуется 1,5 кг пенициллина каждый день, чтобы жить; каждая больница получает этот 1 кг препарата каждый день; поэтому X должен посещать ровно 2 больницы каждый день; он переедет в любую часть страны, но он не хочет путешествовать каждый день очень далеко
• генетика - точки люди; мы хотим найти двух людей, у которых самая близкая ДНК (она не позволяет нам рассчитать расстояние между двумя людьми); Зачем? потому что, например, они хотят узнать, насколько мы близки друг к другу, и каково наименьшее количество нуклеотидов, которые мы должны изменить в человеке, чтобы сделать его достаточно другим.
• genetics II - точки - это люди, но мы измеряем расстояние между они выглядят; например мы близки к уничтожению, и нам нужно отправить человека в миссию, где он, скорее всего, умрет; и у нас есть устройство, необходимое для выполнения миссии, но она работает только для одного человека, которого он признает внешность (и это механизм проверки является очень точным), поэтому нам нужно найти два, как похожие человек, как это возможно

дальняя пара точек:

• тестирование - мы успешно протестировали телепортировался на наименьшее расстояние, крайний рядом, поэтому мы хотим, чтобы проверить его как можно тщательнее; поэтому нам нужно найти две лаборатории, которые находятся как можно дальше друг от друга
• побег/безопасность - постполяционный мир; только некоторые места (точки) пригодны для жилья; люди могут жить на одном из них, так как им нужно быть рядом друг с другом для обеспечения безопасности (их мало); но жизнь в каком-то месте может вызвать химическое облако (смертельное), которое будет расширяться до неизвестных размеров; и это может произойти только однажды по какой-то причине; поэтому они должны жить в таком месте, где они могут найти как можно более дальнюю другую среду обитания.
• genetics - мы хотим найти как можно больше двух организмов, чтобы поэкспериментировать с ними и получить еще более разнообразные виды или просто проверить, насколько разнообразны, например млекопитающие могут быть

Я знаю, что это «Литт» надуманным, но важные обычаи перед дефисом (тестирование, генетика и т.д.). Вместо телепортеров может быть что-то еще, более вероятно существовать, но использование одного и того же. Могут быть другие практические применения для поиска двух, поскольку подобные организмы возможны, но я должен был бы спросить генетика. Но не стесняйтесь писать больше практических историй для моих обычаев.

Было бы превосходно иметь пример для больших размеров.

Answer 1

Приложения ближайшей пары.

Следующие алгоритмы и приложения могут быть эффективно реализованы с использованием ближайших парных структур данных или связаны с ближайшими парными вычислениями как важными подпрограммами.

1. Динамические минимального остовного дерева
2. Две оптимизации эвристики в комбинаторной оптимизации
3. Прямые скелетов и конструкции крыши
4. диаграмма Ray-пересечение
5. Другие приложения обнаружения коллизий
6. Иерархическая кластеризация
7. Эвристика для путешествующих продавцов
8. Жадные соответствие
9. Конструктивная индукция
10. базисы Грёбнера

Source

Что касается ваших идей:

1. тестирования Да это будет работать, но более реалистичный пример может быть легко нашли, подумали о чем-то в авиационной промышленности (например).
2. много путешествий Мы можем написать это как «расстояние для путешествия», и да, это тоже может работать.
3. genetics I & II Примеры тоже не ошибаются, но немного размыты.

---

Применение дальней пары.

О ваших идеях, опять же они не кажутся неправильными, но, как вы говорите, немного надуманными.

---

пример для больших размеров.

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