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