• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Odległość punktów w przestrzeni

VPS Starter Arubacloud
0 głosów
300 wizyt
pytanie zadane 23 marca 2023 w Algorytmy przez polandonion Mądrala (6,970 p.)
edycja 23 marca 2023 przez polandonion
Siema, mam nietypowy problem algorytmiczny: Dany jest zbiór punktów w przestrzeni trójwymiarowej A = {P1, P2, P3, ...}. Dla każdego z nich trzeba podać odległość do najbardziej oddalonego, od niego samego, punktu. Dla uproszczenia liczenia przyjmijmy, że odległość punktów: A = (x, y, z) oraz A' = (x', y', z') wyraża się wzorem:

|AB| = |x - x'| + |y - y'| + |z - z'|

Ma ktoś pomysł inny od O(n^2)?
komentarz 23 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Nie wiem jak to zrobić, ale wydaje mi się, że z geometrią analityczną nie będzie miało to wiele wspólnego.
komentarz 23 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Najpierw zastanowiłbym się nad przypadkiem dwuwymiarowym.
komentarz 23 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Nie zdziwiłbym się jakby jakieś zamiatanie albo coś tego typu weszlo
komentarz 23 marca 2023 przez polandonion Mądrala (6,970 p.)
a w jaki sposob moznaby tutaj uzyc zamiatania?
komentarz 23 marca 2023 przez Whistleroosh Maniak (56,900 p.)
Gdyby to była metryka euklidesowa to najdalszy punkt zawsze by się znajdował na otoczce wypukłej. Nie wiem natomiast jak to wygląda w przypadku metryki miejskiej
komentarz 24 marca 2023 przez tkz Nałogowiec (42,000 p.)
Coś z tyłu głowy mi mówi by użyć octree, który ma n logn, ale czy to prawda, to nie wiem.
komentarz 24 marca 2023 przez reaktywny Nałogowiec (40,650 p.)
Trudny problem. Jestem ciekaw jak finalnie go rozwiążesz
komentarz 24 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@tkz, 

Co to o octree? 

komentarz 24 marca 2023 przez tkz Nałogowiec (42,000 p.)
"Sześcienny diagram" (ang. "octree") to struktura drzewiasta wykorzystywana w przetwarzaniu graficznym i analizie danych pomiarowych w przestrzeni trójwymiarowej. Służy do organizowania przestrzeni trójwymiarowej na sposób hierarchiczny, poprzez podział jej na sześcienne regiony (oktany).

1 odpowiedź

0 głosów
odpowiedź 24 marca 2023 przez Whistleroosh Maniak (56,900 p.)

Przyjrzałbym się na początku co się dzieje w przypadku 2d. Wtedy wydaje mi się, że wystarczy policzyć coś w stylu minimum bounding rectangle (tylko ten prostokąt będzie obrócony o 45 stopni) i punkty najbardziej od dowolnego punktu zawsze będą na krawędzi tego prostokąta:

Tutaj czarne to punkty, czerwone to minimum bounding rectangle. Spójrzmy na ten czarny punkt w środku. Wszystkie punkty jasno zielone są w odległości 1 od tego punktu, ciemniej zielone w odległości 2, a jeszcze ciemniej w 3. Zatem widać, że ten najbardziej oddalony będzie gdzieś na krawędzi tego bounding rectangle. Zatem wystarczy znaleźć krawędzi i wziąć chyba 2 najbardziej skrajne punkty z tej krawędzi i sprawdzić odległość od punktu dla którego szukamy odpowiedzi. Jeśli rozumowanie jest poprawne to o dziwo odpowiedź na zapytanie działa w czasie stałym.

W przypadku 3d prawdopodobnie jest tak samo tylko trzeba uogólnić ten bounding rectanle na 3 wymiary

komentarz 24 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
liczymy te punktu jakoś tak podobnie jak w tym zadaniu binarne loty x+y i x-y ?
komentarz 24 marca 2023 przez Whistleroosh Maniak (56,900 p.)
Pewnie tak. Trzeba tylko wymyślić jak to liczyć w 3d

Podobne pytania

0 głosów
2 odpowiedzi 181 wizyt
0 głosów
1 odpowiedź 240 wizyt
pytanie zadane 14 stycznia 2017 w Matematyka, fizyka, logika przez PieroQQ Początkujący (420 p.)
0 głosów
1 odpowiedź 127 wizyt
pytanie zadane 9 czerwca 2023 w Matematyka, fizyka, logika przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,454 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...