Jaki jest pożytek ze znalezienia minimalnej liczby linii prostych w celu pokrycia zestawu punktów?

Istnieje popularny problem [1] [2] w informatyce, który polega na znalezieniu minimalnej liczby linii prostych pokrywających dany zestaw punktów w 2D.

Mimo że zeskanowałem wiele artykułów, żaden z nich nie ma wyraźnej motywacji do rozwiązania problemu.

Jaki jest pożytek z rozwiązania tego problemu? Czy istnieje dokument, który to wyjaśnia?

Chociaż wiele prac z informatyki teoretycznej twierdzi, że ich praca ma praktyczne zastosowania, niestety często tak nie jest. Zwykle albo problemy są zbyt dalekie od bycia czymś użytecznym (zbyt uproszczonym), albo algorytmy są zbyt dalekie od bycia praktycznym (np. Ukrywanie dużych stałych w notacji O).

Możesz jednak spojrzeć na dokumenty

• Algorytmy aproksymacji uderzania w obiekty liniami prostymi (Hassin i Megiddo) i
• O złożoności lokalizacji obiektów liniowych w płaszczyźnie (Megiddo i Tamir).

Twierdzą, np

Problem trafiania obiektów w samolot przy minimalnej liczbie linii prostych ma zastosowanie wojskowe. W wielu przypadkach, gdy bombowiec próbuje zniszczyć cele na ziemi, chronione przez pociski przeciwlotnicze, musi spędzać jak najmniej czasu w pobliżu celów. Dlatego staranne zaplanowanie nalotu na miejsce z wieloma celami (na przykład klaster zbiorników paliwa) wymaga minimalnej liczby lotów przez bombowiec. Co więcej, każde przejście musi być przeprowadzone tak szybko, jak to możliwe, dlatego dla każdego zanurzenia w miejscu istnieje linia prosta („kij”), wzdłuż której niszczone są cele.

I również:

Na przykład możemy zobaczyć problemy, przed którymi stoi planista, który musi zlokalizować r (liniowe) segmenty nowego systemu kolei, aby zminimalizować średni koszt dla użytkowników, którzy muszą dotrzeć do torów z wielu różnych małych społeczności. Zatem linia prosta lub segment linii ma naturalne znaczenie w tym kontekście. Czasami takie problemy są łatwiejsze niż problemy z urządzeniami punktowymi. Na przykład o wiele łatwiej jest znaleźć linię, aby zminimalizować sumę odległości od zestawu określonych punktów, niż znaleźć pojedynczy punkt o tym samym celu.