Liczba triangulacji zbioru

Po tym, jak tego lata Emo Welzl przemawia na ten temat, wiem, że liczba triangulacji zbioru punktów na płaszczyźnie wynosi między około a . Przepraszam, jeśli jestem nieaktualny; aktualizacje mile widziane. $n$ $\Omega(8.48^n)$ $O(30^n)$

Wspomniałem o tym na zajęciach i chciałem podążać za krótkimi mędrcami, aby dać uczniom poczucie (a) dlaczego tak trudno było ustalić tę ilość i (b) dlaczego tak wielu opieka do paznokci w dół. Odkryłem, że nie miałem odpowiednich odpowiedzi, aby wyjaśnić którąkolwiek z tych kwestii; tyle dla mojej sageness!

Doceniam twoje zdanie na te mgliste pytania. Dzięki!

co.combinatorics cg.comp-geom Joseph O'Rourke
źródło

Według strony poligonizacji Erika Demaine'a granica określona w wykładzie to

, ale nie pamiętam, czy Emo Welzl stwierdził, że można lepiej powiązać, stosując dokładniejszą analizę. Z jakiegoś powodu mam w głowie

O (56^{n})

$O(56^n)$

O (35^{n})

$O(35^n)$

Timothy Sun

Na tej samej stronie jest napisane: „Bieżące najlepsze ograniczenie to 30”. Liczba 56 oznacza poligonizację.

Chao Xu,

Być może warto podać własne odpowiedzi na moje pytania. Triangulacje są tworzone przez nie krzyżujące się segmenty. Zrozumienie braku krzyżowania jest trudne. To jest). W przypadku (b) pościg jest napędzany próbą zrozumienia braku krzyżowania. Myślę, że zgodzisz się, że te odpowiedzi są nieodpowiednie.

Joseph O'Rourke,

Jako punkt odniesienia robienie tego samego dla punktów w pozycji wypukłej jest zadaniem domowym za pomocą liczb katalońskich. Wynika to z tego, że możemy w przyjemny sposób scharakteryzować brak przekraczania granicy poprzez zrównoważone nawiasy (dając wiarygodność punktu (a))

Suresh Venkat,

Chciałbym powiedzieć, że ten problem nie jest bezpośrednio związany z EO. Głównie dlatego, że kluczową kwestią jest charakterystyka nie krzyżujących się par, a także dlatego, że w tym pytaniu jest o wiele silniejszy smak topologiczny niż geometryczny (i mamy poszlakowe dowody, że EDC jest wewnętrznie geometryczny)

Suresh Venkat

Odpowiedzi:

Oto jeszcze jeden „zastosowany” powód, dla którego dbamy o triangulacje. Jest wiele pracy nad kompresją siatki, której celem jest użycie jak najmniejszej liczby bitów na wierzchołek do zakodowania siatki (głównie w celu ułatwienia przechowywania i transmisji). Określona podstawa wykładnika w liczbie triangulacji płaskiego zestawu punktów zapewnia teoretycznie dolną granicę liczby bitów potrzebnych na wierzchołek (w szczególności $8.48^n$ triangulacje oznaczają, że potrzebujesz co najmniej 8,48 bitów na wierzchołek). Takie granice można następnie porównać z rzeczywistymi schematami kompresji siatki, aby określić ich skuteczność.

Suresh Venkat
źródło

Doskonały punkt, Suresh! Nie myślałem o tym związku.

Joseph O'Rourke,

Dolna granica została nieznacznie poprawiona do $\Omega(8.65^n)$ ( patrz tutaj arXiv ). Staram się utrzymać się na bieżąco granic dla różnych wariantów tego problemu w tej strony (przykro o tym bezwstydnym self-reklama).

Bardzo podoba mi się twoje twierdzenie, że problem jest trudny, ponieważ „zrozumienie braku krzyżowania jest trudne”. The $30^n$ granica (i niektóre z poprzednich granic) opiera się na związku między liczbą triangulacji a oczekiwanymi właściwościami losowej triangulacji (wybranymi jednolicie ze zbioru wszystkich możliwych triangulacji zbioru punktów). To przekształca problem w badanie oczekiwanych właściwości losowej triangulacji, co jest trudne, ponieważ brak krzyżowania nie pozwala nam korzystać ze standardowych narzędzi probabilistycznych (np. Nie możemy wybrać każdej krawędzi z pewnym prawdopodobieństwem $p$ ponieważ może to powodować niektóre przeprawy). Zatem brak skrzyżowania zmusza nas do opracowania nowych metod badania losowych wykresów.

Adam Sheffer
źródło

to ładna strona internetowa.

Suresh Venkat