Seminar WS 2004/05:
Geometrisches Runden

http://www.mpi-sb.mpg.de/~kettner/courses/rounding_seminar_04/

Dr. Lutz Kettner , Prof. Dr. Kurt Mehlhorn und Dr. Susanne Schmitt

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:

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.

Voraussetzungen

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.

Betreuerinnen und Betreuer

Dr. Lutz Kettner Geb. 46 (MPII), Raum 306
Dr. Susanne Schmitt     Geb. 46 (MPII), Raum 318

Termine

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.

Vorträge

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.  


Lutz Kettner (<surname>@mpi-inf.mpg.de). Last modified on Tuesday, 17-Jan-2006 17:53:43 MET.