Znaleźć centralny punkt w zestawie punktów metrycznych przestrzeni, w mniej niż ?

Mam zestaw punktów, które są zdefiniowane w przestrzeni metrycznej - więc mogę zmierzyć „odległość” między punktami, ale nic więcej. Chcę znaleźć najbardziej centralny punkt w tym zestawie, który definiuję jako punkt o minimalnej sumie odległości do wszystkich innych punktów. Obliczenia metryczne są powolne, więc w miarę możliwości należy go unikać. $n$

Oczywisty sposób znalezienia tego punktu polega na obliczeniu metrycznej odległości , ponieważ po prostu (a) oblicza dla każdego punktu sumę odległości do wszystkich innych punktów, a następnie (b) przyjmuje punkt minimalny. $n^2$

Czy istnieje sposób, aby to zrobić w porównaniach odległości mniejszych niż ? (Prawdopodobnie w jakiś sposób wykorzystuje nierówność trójkąta, co powinno trzymać się mojej metryki.) $O(n^2)$

Dobre przybliżenie może wystarczyć, jeśli nie istnieje dokładna metoda.

— Logistyka otwartych drzwi
źródło

Bez nierówności trójkąta (lub innego sposobu uzyskiwania informacji o niezmierzonych krawędziach) jedynym rozwiązaniem jest ; widać to po antagonistycznym argumencie.

O (n^{2})

$O(n^2)$

— Kittsil,

Załóżmy, że nierówność trójkąta jest dostępna - tak powinno być dla mojej metryki.

— Logistyka otwartych drzwi

Zasadniczo jest to obliczanie radia z wykresu z równością trójkątów.

— Kaveh,

@Kaveh Chyba masz na myśli promień ... chyba że wykres ma zepsutą krawędź. Dbam o to, ponieważ mam zbyt dużo słownictwa, którego nie znam. --- Ale jest to wtedy kompletny wykres, a rozmiar wejściowy to tylko liczba wierzchołków.

— babou

@OpenDoorLogistics Jeśli nie ma nierówności trójkąta, z definicji nie jest to przestrzeń metryczna. Proszę wyjaśnić pytanie: jeśli wiesz, że jest to przestrzeń metryczna, to wiesz, że ma nierówność trójkąta; jeśli nie wiesz, że ma nierówność trójkąta, nie możesz twierdzić, że jest to przestrzeń metryczna.

— David Richerby,

Odpowiedzi:

Nie. W najgorszym przypadku nie można zrobić lepiej niż . $\Theta(n^2)$

Rozważ rozmieszczenie punktów, w których każda para punktów znajduje się w odległości od siebie. (Jest to możliwa konfiguracja.) W takim razie nie możesz zrobić nic lepszego niż zbadanie każdej krawędzi. W szczególności, jeśli istnieje jakaś krawędź, której nie zbadałeś, przeciwnik może wybrać długość tej krawędzi jako , lub ; wszystkie te wybory są zgodne ze wszystkimi innymi dokonanymi przez ciebie obserwacjami i wymogami metryki (np. z nierównością trójkąta), więc wszystkie trzy są możliwe; ale wymagają różnych wyników. Tak więc, jeśli twój algorytm nie sprawdza tej krawędzi, a następnie coś wypisuje, przeciwnik może zawsze wybrać długość niewybadanego zbocza, co spowoduje nieprawidłowe wyjście twojego algorytmu. $1$ $0.9$ $1.0$ $1.1$

Jeśli jednak wiesz, że wszystkie punkty żyją w (nawet jeśli nie podano ich współrzędnych), problem można rozwiązać, mierząc odległości , zakładając, że nie zwyrodnienia (brak podzbioru punktów jest współpłaszczyznowy). $\mathbb{R}^d$ $O((d+1)n)$ $d+1$

W szczególności losowo wybierz punktów. Będą to punkty kontrolne. Biorąc pod uwagę odległości par, można obliczyć dla nich współrzędne, które są zgodne z ich odległościami par. Teraz dla każdego innego punktu oblicz odległość od do każdego z punktów kontrolnych. Korzystanie triangulacji i te odległości można obliczyć położenie w stosunku do punktów kontrolnych, a zatem współrzędne . Zrób to dla każdego nie-Anchor Point . Teraz masz współrzędne dla każdego punktu i możesz użyć tych współrzędnych, aby znaleźć punkt centralny, nie prosząc wyroczni o podanie dalszych odległości parami. Nie wiem, czy ten ostatni krok można zrobić szybciej niż $d+1$ $P$ $P$ $P$ $P$ $P$ $O(n^2)$ czasu , ale może być zrobione bez żadnych więcej parami pomiaru odległości.

— DW
źródło

Masz punktów w wymiarze . Nawet spojrzenie na wszystkie współrzędne wejściowe wymaga czasu.

n

$n$

n - 1

$n-1$

Θ (n^{2})

$\Theta(n^2)$

— Louis,

@Louis Pytanie nie mówi nic o wymiarach i nie jest pewne, czy jest to metryka. Wszystko, co mamy, to nierówność trójkąta. Właściwy pogląd to komentarz Kaveha: jako kompletny wykres. Jest to zgodne z tą odpowiedzią. Ale nie mam pojęcia, czy jest on zgodny z jakąkolwiek stałą miarą, gdy rośnie bez ograniczeń.

n

$n$

— babou,

@DW Dzięki - czy moglibyśmy zrobić coś lepszego w przeciętnym przypadku? Jest to uzasadnione problemem w świecie rzeczywistym, więc dane mogą być „średnie” (cokolwiek to może znaczyć).

— Open Door Logistics,

@all - przepraszam za zamieszanie re: metric (jestem laikiem w teoretycznej CS). Moja funkcja odległości zdecydowanie spełnia 4 kryteria dla przestrzeni metrycznej, zgodnie z definicją linku do przestrzeni metrycznej w Wikipedii .

— Logistyka otwartych drzwi

@OpenDoorLogistics, dodałem jeden specjalny przypadek, w którym wydaje się, że można lepiej.

— DW

Zobacz pracę Piotra Indyka nad szybkimi algorytmami dla przestrzeni metrycznych. ( Sublinear Algorytmy dla problemów przestrzeni metrycznej , w Proceedings of STOC '99 , str. 428–434. ACM, 1999; PS ) Sekcja 3 podaje algorytm w przybliżeniu 1-środkowy algorytm w czasie liniowym.

— użytkownik71641
źródło

Czy mógłbyś podać streszczenie algorytmu? Idealnie szukamy pełnych odpowiedzi, a nie linków do treści zewnętrznych.

— David Richerby

Przepraszamy za bardzo powolną odpowiedź. Oczywiście nie sprawdzam często StackExchange. Wydaje mi się, że napisanie streszczenia w połowie przyzwoitego zajęłoby mi ponad godzinę, podczas gdy praca Piotra jest pięknie napisana, bardzo dokładnie wyjaśnia algorytm i zawiera wszystkie dokładne definicje. Dlatego osobiście zdecydowanie zalecałbym korzystanie z tej wysokiej jakości treści zewnętrznych, zamiast ze średniej jakości treści wewnętrznych, które mogłem wyprodukować. Krótka odpowiedź brzmi: jeśli chcesz po prostu znaleźć przybliżoną medianę, możesz to zrobić w czasie liniowym O (n).

— user71641,