Problemy z bliskością

Problemy bliskości to klasa problemów z geometrii obliczeniowej , które obejmują szacowanie odległości pomiędzy obiektami geometrycznymi.

Podzbiór tych problemów wyrażonych wyłącznie w kategoriach punktów jest czasami nazywany problemami najbliższego punktu , chociaż termin „problem najbliższego punktu” jest również używany jako synonim wyszukiwania najbliższego sąsiada .

Wspólną cechą wielu z tych problemów jest możliwość ustalenia dolnej granicy Θ ( n log n ) ich złożoności obliczeniowej poprzez redukcję problemu niepowtarzalności elementów w oparciu o obserwację, że jeśli istnieje skuteczny algorytm do obliczenia pewnego rodzaju minimalnego odległości dla zbioru obiektów, sprawdzenie, czy odległość ta jest równa 0, jest banalne.

Problemy atomowe

Chociaż problemy te nie stanowią wyzwania pod względem złożoności obliczeniowej, niektóre z nich są godne uwagi ze względu na ich wszechobecność w komputerowych zastosowaniach geometrii.

• Odległość pomiędzy parą odcinków linii . Nie można jej wyrazić jednym wzorem, tak jak np. odległość punktu od prostej . Jego obliczenie wymaga dokładnego wyliczenia możliwych konfiguracji, zwłaszcza w wymiarach 3D i wyższych.
• Obwiednia , minimalny hiperprostokąt wyrównany do osi , który zawiera wszystkie dane geometryczne

Problemy z punktami

• Najbliższa para punktów : mając N punktów, znajdź dwa o najmniejszej odległości między nimi
• Zapytanie o najbliższy punkt / zapytanie o najbliższego sąsiada : Mając N punktów, znajdź taki, który ma najmniejszą odległość do danego punktu zapytania
• Problem wszystkich najbliższych sąsiadów (konstrukcja grafu najbliższego sąsiada ): Mając N punktów, znajdź dla każdego z nich najbliższy
• Średnica zbioru punktów : mając N punktów, znajdź dwa o największej odległości między nimi
• Szerokość zbioru punktów: mając N punktów, znajdź dwie (hiper)płaszczyzny o najmniejszej odległości między nimi i ze wszystkimi punktami między nimi
• Minimalne drzewo rozpinające dla zbioru punktów
  • Minimalne drzewo rozpinające euklidesowe
• Triangulacja Delaunaya
• Schemat Woronoja
• Najmniejsza otaczająca kula : mając N punktów, znajdź najmniejszą kulę (okrąg) obejmującą je wszystkie
• Największy pusty okrąg : mając N punktów na płaszczyźnie, znajdź największy okrąg wyśrodkowany w ich wypukłym kadłubie i nie obejmujący żadnego z nich
• Najmniejszy prostokąt otaczający : w przeciwieństwie do wspomnianego powyżej problemu z obwiednią , prostokąt może mieć dowolną orientację
• Największy pusty prostokąt
• Klucz geometryczny , graf ważony na zbiorze punktów jako jego wierzchołkach, który dla każdej pary wierzchołków ma między nimi ścieżkę o wadze co najwyżej „k” razy odległość przestrzenna między tymi punktami dla ustalonego „k”.

Inny

• Najkrótsza ścieżka wśród przeszkód
• Odległość najbliższego podejścia

•         Franco P. Preparata i Michael Ian Shamos (1985). Geometria obliczeniowa — wprowadzenie . Springer-Verlag . ISBN 0-387-96131-3 . Wydanie pierwsze: ISBN 0-387-96131-3 ; Wydanie drugie, poprawione i rozszerzone, 1988: ISBN 3-540-96131-3 ; Tłumaczenie rosyjskie, 1989: ISBN 5-03-001041-6 . Problemy bliskości zostały omówione w rozdziałach 6 i 7.