Co jest naprawdę dobrym problemem, aby ubrudzić sobie ręce w geometrii obliczeniowej?

Geometria obliczeniowa jest obszarem, który wydaje mi się bardzo interesujący i chciałbym poświęcić około miesiąca lub dwóch na projekt, który zapozna mnie z tym i pomoże mi nauczyć się kluczowych pojęć.

Jaki jest dobry sposób podejścia do tego i jakie są kluczowe koncepcje, których powinienem się upewnić?

Aby połączyć sugestie Suresha V. i Dave'a C., fajną może być próba uzyskania dowodów eksperymentalnych na nierozwiązany problem poprzez wdrożenie niezbędnych algorytmów. Na przykład obecnie wiadomo, że triangulacja Delaunaya nie jest ( / 2) kluczem [Prosenjit Bose, Luc Devroye, Maarten Löffler, Jack Snoeyink, Vishal Verma: „Współczynnik rozpięcia triangulacji Delaunay jest większy niż / 2. ” CCCG 2009 : 165-167.] Możesz zaimplementować algorytm triangulacji Delaunaya i najkrótsze ścieżki oraz spróbować eksperymentalnie ustalić, jaki może być prawdziwy współczynnik rozpinania. Lub, co trudniejsze, spróbuj obliczyć kombinatoryczną złożoność diagramu linii Voronoi w$\pi$$\pi$$\mathbb{R}^3$, kolejny nierozwiązany problem (i na liście, którą Suresh wymienia jako Problem 3 ).

Chociaż może to być zbyt zniechęcające, aby wskoczyć, zanim zrobisz to, jak sugeruje Dave, istnieje ładna kolekcja otwartych problemów w geometrii obliczeniowej utrzymywana przez Joe O'Rourke, Erika Demaine i Joe Mitchella. Stanowią one dobrą migawkę podstawowych pytań w dziedzinie teoretycznej.

Uzyskaj problemy z badaniem książki w dyskretnej geometrii . Przeczytaj to, zobacz, które problemy Cię interesują, przeczytaj literaturę, rozwiąż i opublikuj.

Ostrzeżenie: problemy w tej książce są trudne. Jest to jednak doskonałe wprowadzenie do otwartych problemów w terenie i dobry sposób na poznanie pola.

Victor Klee w 1973 roku postawił problem z ochroną prostych wielokątów (czujników chroniących galerię sztuki umieszczoną na jego wierzchołkach), który rozkwitł w setki artykułów dotyczących tego, co stało się znane jako problem galerii sztuki. Wiele podstawowych pomysłów w geometrii obliczeniowej wchodzi w grę podczas badania problemu galerii sztuki (takie jak triangulacja, rozkładanie wielokątów na kawałki o specjalnych właściwościach, wykresy widoczności itp.) Cudownie napisana książka Joe O'Rourkego nadal jest świetną wprowadzenie do pomysłów i metod tutaj, a książka jest dostępna w części lub w całości za darmo na tej stronie:

http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html

Myślę, że to świetny punkt wejścia do geometrii obliczeniowej.

Jeff Erickson „ JeffE ” ma także ładny zestaw wskazówek na ten temat: http://compgeom.cs.uiuc.edu/~jeffe/compgeom/ . Ponieważ często odwiedza TCS SE, może ci pomóc znacznie lepiej.

Kup książkę taką jak ta , zaimplementuj algorytmy i znajdź przykład lub mały projekt do pracy z sekcji ćwiczeń. Tu i tutaj znajduje się lista wielu pomysłów na projekty. Google powinien ujawnić wiele innych. Wybierz taki, który brzmi zabawnie i idź po niego.