Какая польза от нахождения минимального количества прямых линий для покрытия множества точек?

12

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

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

Какая польза от решения этой проблемы? Есть ли бумага, которая объясняет это?

падаван
источник
Вы можете ознакомиться с введением в Cover Line Point: Easy Kernel по существу плотный (Kratsch, Philip & Ray).
Пол GD
Одним из приложений может быть дерандомизация мешков ( en.wikipedia.org/wiki/Bootstrap_aggregating ) в статистике.
Луи

Ответы:

15

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

Тем не менее, вы можете посмотреть на документы

Они утверждают, например,

Проблема поражения объектов на плоскости с минимальным количеством прямых линий имеет военное применение. Во многих случаях, когда бомбардировщик пытается уничтожить цели на земле, защищенные зенитными ракетами, он должен проводить как можно меньше времени рядом с целями. Таким образом, тщательное планирование воздушного налета на многоцелевой объект (например, кластер топливных баков) требует минимального количества раз, когда бомбардировщик должен пролетать через объект. Более того, каждый проход должен выполняться как можно быстрее, поэтому для каждого погружения на площадку существует прямая линия («палка»), вдоль которой уничтожаются цели.

А также:

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

Пол Г.Д.
источник
1
Это было бы идеальным предложением для представления статьи (не моей).
падаван
3
Бомбы! взрывы! убийство! уничтожить! Я не думаю, что приложения могут стать более практичными, чем это :)
Томас,