Problem miary Klee

Zestaw prostokątnych zakresów („krata”), których pole ma zostać zmierzone.

W geometrii obliczeniowej problem miary Klee polega na określeniu, jak wydajnie można obliczyć miarę sumy ( wielowymiarowych ) zakresów prostokątnych. Tutaj d -wymiarowy prostokątny zakres jest definiowany jako iloczyn kartezjański d przedziałów liczb rzeczywistych , który jest podzbiorem R ^d .

Problem został nazwany na cześć Victora Klee , który podał algorytm obliczania długości sumy przedziałów (przypadek d = 1), który później okazał się optymalnie wydajny w sensie teorii złożoności obliczeniowej . Złożoność obliczeniowa obliczania obszaru sumy dwuwymiarowych zakresów prostokątnych jest obecnie również znana, ale przypadek d ≥ 3 pozostaje problemem otwartym .

Historia i algorytmy

W 1977 roku Victor Klee rozważał następujący problem: biorąc pod uwagę zbiór n przedziałów w prostej rzeczywistej , obliczyć długość ich sumy. Następnie przedstawił algorytm rozwiązania tego problemu ze $O$ obliczeniową lub „czasem działania”) aby poznać znaczenie tego stwierdzenia. Algorytm ten oparty na sortowaniu interwały, jak później Michael Fredman i Bruce Weide (1978) wykazali jako optymalne.

Później, w 1977 roku, Jon Bentley rozważał dwuwymiarową analogię tego problemu: biorąc pod uwagę zbiór n prostokątów , znajdź obszar ich sumy. Uzyskał również algorytm złożoności $wymiarowych$ obecnie znany jako algorytm , na redukcji problemu do problemów 1 : odbywa się to poprzez linię wzdłuż obszaru. Korzystając z tej metody, obszar związku można obliczyć bez jawnego konstruowania samego związku. Algorytm Bentleya jest obecnie znany również jako optymalny (w przypadku dwuwymiarowym) i jest używany w grafika komputerowa m.in.

Te dwa problemy są 1- i 2-wymiarowymi przypadkami bardziej ogólnego pytania: biorąc pod uwagę zbiór nd - wymiarowych prostokątnych zakresów, oblicz miarę ich sumy. Ten ogólny problem to problem miary Klee.

Po uogólnieniu na przypadek d -wymiarowy, algorytm Bentleya ma czas działania ${\ Displaystyle O (n ^ {d-1} \ log n)}$ . Okazuje się nie jest to optymalne, ponieważ rozkłada d -wymiarowy problem tylko na n ( d-1 )-wymiarowe problemy i nie rozkłada dalej tych podproblemów. W 1981 roku Jan van Leeuwen i Derek Wood poprawili czas działania tego algorytmu do ${\ Displaystyle O (n ^ {d-1})}$ dla re ≥ 3 przy użyciu dynamicznych drzew czworokątnych .

W 1988 roku $Overmars$ i algorytm ≥ 3. określoną strukturę danych podobne do kd-tree, aby rozłożyć problem na dwuwymiarowe komponenty i wydajnie agregować te komponenty; same problemy dwuwymiarowe są skutecznie rozwiązywane za pomocą kraty Struktura. Chociaż jest asymptotycznie szybszy niż algorytm Bentleya, jego struktury danych zajmują znacznie więcej miejsca, dlatego jest używany tylko w problemach, w których n lub d jest duże. W 1998 roku Bogdan Chlebus zaproponował prostszy algorytm z takim samym asymptotycznym czasem działania dla typowych przypadków specjalnych, w których d wynosi 3 lub 4.

W 2013 roku Timothy M. Chan opracował prostszy algorytm, który unika potrzeby stosowania dynamicznych struktur danych i eliminuje czynnik logarytmiczny, obniżając najlepszy znany czas działania dla re ≥ 3 do ${\ Displaystyle O (n ^ {d/2})}$ .

Znane granice

Jedyną znaną dolną granicą dowolnego d jest , $.$ z tym czasem działania są znane dla = d 2 Algorytm Chan zapewnia górną granicę dla d ≥ 3, więc dla d ${\ Displaystyle O (n ^ {d/2})}$ ≥ 3, pozostaje kwestią otwartą, czy możliwe są szybsze algorytmy lub alternatywnie, czy można udowodnić ściślejsze dolne granice. W szczególności pozostaje otwarte, czy czas działania algorytmu musi zależeć od d . Ponadto pytanie, czy istnieją szybsze algorytmy, które radzą sobie ze specjalnymi przypadkami (na przykład, gdy współrzędne wejściowe są liczbami całkowitymi w ograniczonym zakresie), pozostaje otwarte.

$liczbę punktów przebicia wymaganych$ można rozwiązać w p oznacza (suma przebity wspólnym punktem można obliczyć w czasie liniowym, obliczając ekstrema). Parametr p jest parametrem adaptacyjnym, który zależy od konfiguracji wejściowej, a algorytm przebijający daje algorytm adaptacyjny dla problemu miary Klee.

Zobacz też

• Przybliżenie objętości wypukłej , wydajny algorytm dla ciał wypukłych

Referencje i dalsze czytanie

Ważne dokumenty

•   $\ Displaystyle O (n \ log n)}$ Victor ( $1977$ miarę można $w$ niż kroki?”, American Mathematical Monthly , 84 (4): 284–285, doi : 10,2307/2318871 , JSTOR 2318871 , MR 0436661 .
• Bentley, Jon L. (1977), Algorytmy dla problemów z prostokątem Klee , niepublikowane notatki, Wydział Informatyki, Carnegie Mellon University .
•    Fredman, Michael L .; Weide , Bruce ( $,$ „Złożoność obliczania miary Communications the , ): 540–544, doi : 10.1145/359545.359553 , MR 0495193 , S2CID 16493364 .
•   van Leeuwen, Jan ; Wood, Derick (1981), „Problem miary dla zakresów prostokątnych w przestrzeni d ”, Journal of Algorithms , 2 (3): 282–300, doi : 10.1016/0196-6774 (81) 90027-4 , hdl : 1874 /15897 , MR 0632450 .
•   Overmars, Mark H. ; Yap, Chee-Keng (1991), „Nowe górne granice problemu miary Klee”, SIAM Journal on Computing , 20 (6): 1034–1045, doi : 10,1137/0220065 , hdl : 1874/16614 , MR 1135747 .
•   Chlebus, Bogdan S. (1998), „O problemie miary Klee w małych wymiarach”, Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM-98) , Lecture Notes in Computer Science , tom. 1521, Berlin: Springer-Verlag, s. 304–311 , doi : 10.1007/3-540-49477-4_22 , ISBN 978-3-540-65260-1 .
•     Chan, Timothy M. (2013), „Łatwy problem miary Klee”, Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS) (PDF) , s. 410–419, CiteSeerX 10.1.1.643.26 , doi : 10.1109/FOCS.2013.51 , ISBN 978-0-7695-5135-7 , S2CID 11648588 .

Literatura drugorzędna

• Franco P. Preparata i Michael I. Shamos (1985). Geometria obliczeniowa (Springer-Verlag, Berlin).
• Klee's Measure Problem , z listy otwartych problemów w geometrii obliczeniowej sporządzonej przez profesora Jeffa Ericksona . (Dostęp 8 listopada 2005 r., kiedy ostatnia aktualizacja miała miejsce 31 lipca 1998 r.)