Was ist ein wirklich gutes Problem, um sich in der Computergeometrie die Hände schmutzig zu machen?

12

Computergeometrie ist ein Bereich, den ich sehr interessant finde, und ich würde gerne ein oder zwei Monate für ein Projekt verwenden, das mich in dieses Thema einführt und mir hilft, wichtige Konzepte zu erlernen.

Was ist ein guter Weg, um dies zu erreichen, und was sind die Schlüsselkonzepte, bei denen ich sicher sein sollte, dass ich auch vorgestellt werde?


quelle
2
(Zunge fest in der Wange): Lies den Geomblog !! ( geomblog.blogspot.com )
Suresh Venkat
Suchen Sie ein Programmierprojekt, ein theoretisches Projekt oder eine Mischung aus beidem?
James King

Antworten:

8

Um die Vorschläge von Suresh V. und Dave C. zu kombinieren, könnte es Spaß machen, experimentelle Beweise für ein ungelöstes Problem durch Implementierung der erforderlichen Algorithmen zu erhalten. Zum Beispiel ist jetzt bekannt, dass die Delaunay-Triangulation kein ( / 2) -Spanner ist [Prosenjit Bose, Luc Devroye, Jack Snoeyink, Maarten Löffler, Vishal Verma: "Das Überbrückungsverhältnis der Delaunay-Triangulation ist größer als πππ / 2. " CCCG 2009 : 165-167.] Sie könnten einen Delaunay-Triangulationsalgorithmus und kürzeste Pfade implementieren und versuchen, experimentell zu bestimmen, wie hoch das tatsächliche Spanning-Verhältnis sein könnte. Oder versuchen Sie herausfordernder, die kombinatorische Komplexität des Voronoi-Liniendiagramms in R 3 zu berechnenR3ein weiteres ungelöstes Problem (und in der Liste, die Suresh als Problem 3 erwähnt )

Joseph O'Rourke
quelle
2
Dieser letzte Vorschlag ist MEAN!
Jeffs
1
Ja, "anspruchsvoller" ist eine Untertreibung! Vorbehalt Emptor!
Joseph O'Rourke
7

Dies ist zwar zu entmutigend, als dass Sie es vorher tun könnten, wie Dave vorschlägt, aber es gibt eine schöne Sammlung offener Probleme in der Berechnungsgeometrie die von Joe O'Rourke, Erik Demaine und Joe Mitchell gepflegt werden. Diese liefern eine gute Momentaufnahme der Kernfragen im theoretischen Bereich.

Suresh Venkat
quelle
6

Hol das Buch Forschungsprobleme in diskreter Geometrie . Lesen Sie es durch, finden Sie heraus, welche Probleme Sie interessieren, lesen Sie die Literatur, lösen Sie sie und veröffentlichen Sie sie.

Warnung: Die Probleme in diesem Buch sind schwer. Es ist jedoch eine hervorragende Einführung in offene Probleme auf dem Gebiet und eine gute Möglichkeit, etwas über das Gebiet zu lernen.

Sariel Har-Peled
quelle
5

Victor Klee stellte 1973 ein Problem mit der Bewachung einfacher Polygone (Sensoren zum Schutz einer an ihren Scheitelpunkten platzierten Kunstgalerie) auf, das zu Hunderten von Arbeiten über das sogenannte Kunstgalerieproblem aufblühte. Viele der Grundideen der Computergeometrie kommen beim Studium des Kunstgalerie-Problems zum Tragen (Dinge wie Triangulation, Zerlegung von Polygonen in Stücke mit besonderen Eigenschaften, Sichtbarkeitsgraphen usw.). Joe O'Rourkes wunderbar gut geschriebenes Buch ist immer noch ein großartiges Buch Einführung in die Ideen und Methoden hier, und das Buch ist teilweise oder ganz kostenlos auf dieser Website erhältlich:

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

Ich denke, dies ist ein guter Einstieg in die Computergeometrie.

Joseph Malkevitch
quelle
1
Danke, Joe! Und wenn ich hinzufügen darf, es bleiben hier ungelöste Probleme, die zu meinem Vorschlag passen könnten, Ihre Energie auf ein offenes Problem zu lenken. Das macht es spannender. :-)
Joseph O'Rourke
4

Kaufen Sie ein Buch wie dieses , implementieren Sie die Algorithmen und finden Sie im Übungsabschnitt ein Beispiel oder ein kleines Projekt heraus, an dem Sie arbeiten können. Hier und hier sind Listen mit vielen Projektideen. Google sollte viele andere enthüllen. Suchen Sie sich eine aus, die Spaß macht, und versuchen Sie es.

Dave Clarke
quelle