Geometrisches Runden vereinfacht die Darstellung von geometrischen Objekten während es wichtige Eigenschaften erhält. Man möchte zum Beispiel die Punkte einer planaren Karte auf ganzzahlige Koordinaten runden, aber die Topologie der Karte nicht verändern.
Geometrisches Runden hat zwei wichtige Anwendungen:
Geometrische Konstruktionen, wie die eines Schnittpunkts zweier Geradensegmente, erzeugen neue geometrische Objekte deren exakte Repräsentation höhere Genauigkeit, zum Beispiel mehr bits für die Koordinaten, braucht. Man kann mit so einem Ansatz korrekte und auch sehr effiziente Programme schreiben, aber die Daten lassen sich gewöhnlich nicht mehr in gängigen Dateiformaten und Schnittstellen zu anderen Programmen verwenden. Die Objekte müssen gerundet werden.
Die höhere Genauigkeit, die nötig wird bei konstruierten Objekten, macht Operationen auf diesen Objekten langsamer. Werden konstruierte Objekte wieder als Ausgangspunkt für neue Konstruktionen verwendet, sogenannte kaskadierte Konstruktionen, wie sie zum Beispiel in CAD Systemem beim Entwurf auftreten, wird das Problem gravierend. Als Lösung kann man zwischendurch die konstruierten Objekte wieder zu einer geringeren Genauigkeit runden.
Das Problem des geometrischen Rundens wird durch die zu respektierenden Eigenschaften der Objekte schwierig. Viele Versionen des Problems sind NP-hart. Wir werden in dem Seminar den aktuellen Stand der Forschung an Hand ausgewählter Artikel kennenlernen, insbesondere die wenigen effizienten Methoden für das Runden von Arrangements in der Ebene und im Raum. Im Anschluss an das Seminar werden Fopra's, Bachelor, und Master Arbeiten zu diesem Thema angeboten.
Das Seminar wird im Rahmen unseres EXACUS Projektes, Efficient and Exact Algorithms for Curves and Surfaces, angeboten.
Wir lesen aktuelle Forschungsartikel (in Englisch). Es kann zum Verständnis eines Artikel durchaus nötig sein, Grundlagen in Textbüchern oder anderen Artikeln nachzulesen. Die Seminarteilnehmer sollten Kenntnisse in Algorithmen, Datenstrukturen und Geometrie, am besten Algorithmische Geometrie, haben.
| Dr. Lutz Kettner | Geb. 46 (MPII), Raum 306 |
| Dr. Susanne Schmitt | Geb. 46 (MPII), Raum 318 |
Die Vorbesprechung findet am 21. Oktober um 14 Uhr c.t. im Raum 021 im Geb. 46 (MPII) statt.
Das Seminar findet jeweils Donnerstag, 14 Uhr c.t., im Raum 021, Gebäude 46 (MPII) statt.
The presentations have to be prepared and discussed in advance with the assistent listed in the table below. You have to read and understand the paper and prepare an outline of your presentation two weeks in advance for discussion with your assistent, and you have to prepare the full presentation one week before your talk for a second discussion. If you have problems understanding the paper, talk to your assistent early enough to not miss these deadlines.
The presentations are in English and last 45 minutes. If the speaker feels uncomfortable with English, he can switch to German, but the slides need to be prepared in English.
(Remark: The articles were available for participants of the seminar and are no longer available.)
| Datum Betreuer |
Thema | Vortragender |
|---|---|---|
| 2.12.04 L.K. |
Finding compact coordinate representations for polygons and polyhedra. V. Milenkovic und L. Nackman. IBM Journal of Research and Development, vol. 34, no. 35, September 1990, pp. 753-769. | Vitaly Osipov |
| 9.12.04 S.S. |
Rounding Arrangements Dynamically. L. Guibas and D. Marimont. Proceedings of the 11th annual symposium on Computational geometry, Vancouver, British Columbia, Canada, pp. 190 - 199, 1995. | Michael Kerber |
| 13.1.05 S.S. |
Snap rounding line segments efficiently in two and three dimensions. M. Goodrich, L. Guibas, J. Hershberger und P. Tanenbaum. Proceedings of the 13th annual symposium on Computational geometry, Nice, France, pp. 284 - 293 1997. | Sascha Kiefer |
| 20.1.05 L.K. |
Shortest Path Geometric Rounding. V. Milenkovic. Algorithmica 27(1): pp. 57-86, 2000. | David Steurer |
| 27.1.05 S.S. |
Inner and outer rounding of set operations on lattice polygonal regions. O. Devillers and P. Guigue. Proceedings of the 20th annual symposium on Computational geometry, Brooklyn, New York, pp. 429 - 437, 2004. | Roman Adam |
| 3.2.05 L.K. |
Testing Homotopy for paths in the plane. S. Cabello, Y. Liu, A. Mantler und J. Snoeyink. Proceedings of the 18th annual symposium on Computational geometry, Barcelona, Spain, pp. 160 - 169, 2002. | Murat Baktiev |
| --.--. | Vertex-rounding a three-dimensional polyhedral subdivision. S. Fortune. Proceedings of the 14th annual symposium on Computational geometry, Minneapolis, Minnesota, pp. 116 - 125, 1998. | |
| --.--. | Polyhedral Modeling With Multiprecision Integer Arithmetic. S. Fortune. Computer-Aided Design, 29(2):123-133, 1997. |