{"id":974,"date":"2014-11-07T15:43:07","date_gmt":"2014-11-07T14:43:07","guid":{"rendered":"http:\/\/www-ma2.upc.es\/vera\/?page_id=974"},"modified":"2015-08-24T17:59:48","modified_gmt":"2015-08-24T16:59:48","slug":"geometric-algorithms","status":"publish","type":"page","link":"https:\/\/dccg.upc.edu\/people\/vera\/teaching\/courses\/geometric-algorithms\/","title":{"rendered":"Geometric Algorithms &#8211; MIRI"},"content":{"rendered":"<address><strong>Seminars on Innovation and Research in Informatics (MIRI)<\/strong><\/address>\n<address><strong>Specialization in Computer Graphics and Virtual Reality<\/strong><br \/>\nDepartament de Matem\u00e0tica Aplicada II<br \/>\nFacultat d\u2019Inform\u00e0tica de Barcelona<br \/>\nUniversitat Polit\u00e8cnica de Catalunya<\/address>\n<hr \/>\n<blockquote>\n<ul>\n<li><a href=\"#goal\">Goal<\/a><\/li>\n<li><a href=\"#contents\">Contents<\/a><\/li>\n<li><a href=\"#links\">Resources<\/a><\/li>\n<li><a href=\"#events\">Related events<\/a><\/li>\n<\/ul>\n<\/blockquote>\n<hr \/>\n<h2><a name=\"goal\"><\/a>Goal<\/h2>\n<p>This seminar is designed as an introduction to geometric algorithms. As the field is far too wide to fit in a short seminar, a strong selection is been done every year. The proposed contents (and related activities) intend to give:<\/p>\n<ul>\n<li>An idea of both the topics and the applications of the field.<\/li>\n<li>The most useful algorithmic tools in the field.<\/li>\n<li>A selection of topics intended for computer graphics students.<\/li>\n<\/ul>\n<hr \/>\n<h2><a name=\"contents\"><\/a>Contents<\/h2>\n<ol>\n<li>Introductory material\n<ul>\n<li><a href=\"http:\/\/www-ma2.upc.es\/geoc\/mat1q1112\/NumbersAndPoints.pdf\">Numbers and points<\/a><\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/geoc\/mat1q1112\/OrientationTests.pdf\">Orientation tests<\/a><\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/geoc\/circumferenciaEN.pdf\">Point in circle<\/a><\/li>\n<\/ul>\n<\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/vera\/wp-content\/uploads\/2014\/11\/GA-MIRI-CH-2D.pdf\">Convex hulls in 2D<\/a><\/li>\n<li>Voronoi diagrams and Delaunay triangulations in 2D\n<ul>\n<li><a href=\"http:\/\/www-ma2.upc.es\/vera\/wp-content\/uploads\/2014\/11\/GA-MIRI-Triangulating-Points.pdf\">Triangulating point sets: introduction<\/a><\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/vera\/wp-content\/uploads\/2014\/11\/GA-MIRI-Voronoi-1-properties.pdf\">Proximity problems, Voronoi diagrams, properties<\/a><\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/vera\/wp-content\/uploads\/2014\/11\/GA-MIRI-Voronoi-2-storing.pdf\">Storing a Voronoi diagram<\/a><\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/vera\/wp-content\/uploads\/2014\/11\/GA-MIRI-Voronoi-3-computing.pdf\">Computing a Voronoi diagram<\/a><\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/vera\/wp-content\/uploads\/2014\/11\/GA-MIRI-Delaunay.pdf\">Triangulating point sets: the Delaunay triangulation<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Duality and its applications\n<ul>\n<li>Suggested references:\n<ul>\n<li>M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, <a href=\"http:\/\/cataleg.upc.edu\/record=b1326857\">Computational Geometry Algorithms and Applications<\/a>, Chapter 8 and, particularly, sections 8.2 and 8.5.<\/li>\n<li>J-D. Boissonat, M. Yvinec, <a href=\"http:\/\/cataleg.upc.edu\/record=b1137324\">Algorithmic Geometry<\/a>, Chapter 7 and, most specially, section 7.1.3.<\/li>\n<li>H. Edesbrunner, <a href=\"http:\/\/cataleg.upc.edu\/record=b1024045\">Algorithms in Combinatorial Geometry<\/a><\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/vera\/teaching\/courses\/discrete-and-algorithmic-geometry\/the-parabola-and-the-circle-dualities-applet\/\">An applet<\/a> to play with<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/vera\/wp-content\/uploads\/2014\/11\/GA2014-duality-Marc-Sunet.pdf\">Slides<\/a> by the student Marc Sunet<\/li>\n<\/ul>\n<\/li>\n<li>Convex hulls in 3D\n<ul>\n<li>Suggested references:\n<ul>\n<li>M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, <a href=\"http:\/\/cataleg.upc.edu\/record=b1326857\">Computational Geometry Algorithms and Applications<\/a>, sections 11.1, 11.2, 11.3 and 11.6.<\/li>\n<li>J. O&#8217;Rourke, <a href=\"http:\/\/cataleg.upc.edu\/record=b1147988\">Computational Geometry in C<\/a><\/li>\n<li>F. P. Preparata, M. I. Shamos, <a href=\"http:\/\/cataleg.upc.edu\/record=b1004185\">Computational Geometry An Introduction<\/a><\/li>\n<li>J-D. Boissonat, M. Yvinec, <a href=\"http:\/\/cataleg.upc.edu\/record=b1137324\">Algorithmic Geometry<\/a>, Chapters 7, 8, and 9.<\/li>\n<li><a href=\"http:\/\/www.cse.unsw.edu.au\/~lambert\/java\/3d\/hull.html\">An applet<\/a> to play with<\/li>\n<\/ul>\n<\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/vera\/wp-content\/uploads\/2014\/11\/GA2014-ConvexHulls3D-Roger-Hernando.pdf\">Slides<\/a> by the student Roger Hernando<\/li>\n<\/ul>\n<\/li>\n<li>Analyzing randomized incremental algorithms: <a href=\"http:\/\/www-ma2.upc.es\/vera\/wp-content\/uploads\/2014\/11\/GA-MIRI-Randomized-incremental.pdf\">An introduction<\/a><\/li>\n<li>Voronoi diagrams and Delaunay tessellations in 3D or with restrictions\n<ul>\n<li>Suggested references:\n<ul>\n<li>Okabe, Boots, Sugihara, Chiu, <a href=\"http:\/\/cataleg.upc.edu\/record=b1167964\">Spatial tessellations: concepts and applications of Voronoi diagrams<\/a><\/li>\n<li>Aurenhammer, Klein, Lee, <a href=\"http:\/\/cataleg.upc.edu\/record=b1430777\">Voronoi diagrams and Delaunay triangulations<\/a><\/li>\n<\/ul>\n<\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/vera\/wp-content\/uploads\/2014\/11\/GA2014-DelaunayWithConstrainsDelaunay3D-Marc-Comino.pdf\">Slides<\/a> by the student Marc Comino<\/li>\n<\/ul>\n<\/li>\n<li>Applying Voronoi diagrams and Delaunay tessellations to shape reconstruction\n<ul>\n<li>Suggested references:\n<ul>\n<li>Crust, anticrust, and beta-skeletons: N. Amenta, M. Bern, D. Eppstein, <a href=\"http:\/\/www-ma2.upc.es\/geoc\/abe-csccr-98.pdf\">The Crust and the Beta-Skeleton: Combinatorial Curve Reconstruction<\/a>, Graphical Models and Image Processing, Vol. 60\/2, No. 2, pp. 125-135, 1998.<\/li>\n<li>Alpha-shapes: H. Edelsbrunner, D. G. Kirkpatrick, R. SeidelAurenhammer, <a href=\"http:\/\/www-ma2.upc.es\/geoc\/eks-sspp-83.pdf\">On the Shape of a Set of Points in the Plane<\/a>, IEEE Transactions on Information Theory, Vol. IT-D, No. 4, pp. 551-559, 1983.<\/li>\n<li>Alpha-shapes: H. Edelsbrunner <a href=\"http:\/\/www.cs.duke.edu\/~edels\/Papers\/2011-B-03-AlphaShapes.pdf\"> Alpha shapes &#8211; A Survey<\/a>.<\/li>\n<li><a href=\"http:\/\/cgm.cs.mcgill.ca\/~godfried\/teaching\/projects97\/belair\/alpha.html\">An applet<\/a> to play with<\/li>\n<\/ul>\n<\/li>\n<li>Slides by the student Miguel \u00c1ngel Vico<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<hr \/>\n<h2><a name=\"links\"><\/a>Resources<\/h2>\n<h3><a name=\"cgal\"><\/a>Computational Geometric Algorithms Library (CGAL)<\/h3>\n<p>Never implement a geometric algorithm before checking if <a href=\"https:\/\/www.cgal.org\/\">CGAL<\/a> has it! It is a reliable and efficient sofware!<\/p>\n<h3><a name=\"latex\"><\/a>Mathematical text editor<\/h3>\n<p>LaTeX is the most extended editor of scientific texts (LaTeX is used to write all the textbooks of scientific publishers as important as Springer, and also most of the mathematics and computer science conferences around the world). It\u2019s a free source software that has versions for all operating systems. You can download LaTeX from <a href=\"http:\/\/www.tug.org\/\" target=\"_blank\">http:\/\/www.tug.org\/<\/a>.<\/p>\n<p>For those of you who work on windows, WinEdt is a very convenient editor for writing LaTeX code. You can download it from <a href=\"http:\/\/www.winedt.com\/\" target=\"_blank\">http:\/\/www.winedt.com\/<\/a>.<\/p>\n<h3><a name=\"ipe\"><\/a>Drawings<\/h3>\n<p>Each person likes preparing his\/her figures with his\/her favorite drawing program. I use IPE (an evolution of xfig designed by a computational geometer), because it allows me to draw the geometric figures that I need, because it integrates text in LaTeX, and because it allows me to also prepare my presentations in a very easy what-you-see-is-what-you-get way. IPE is free source and has versions for all the operating systems. You can download it from <a href=\"http:\/\/ipe7.sourceforge.net\/\" target=\"_blank\">http:\/\/ipe7.sourceforge.net\/<\/a>.<\/p>\n<h3><a name=\"geogebra\"><\/a>Geometric constructions<\/h3>\n<p>In addition to producing your own drawings, you may whish to create and experiment with geometric constructions. If so, we recommend <a href=\"http:\/\/www.geogebra.org\/\" target=\"_blank\">GeoGebra<\/a>.<\/p>\n<hr \/>\n<h2><a name=\"events\"><\/a>Related events<\/h2>\n<ul>\n<li><a href=\"http:\/\/www-ma2.upc.edu\/dccg\/?page_id=736\" target=\"_blank\">DCCG Seminar on Computational Geometry<\/a><\/li>\n<li><a href=\"http:\/\/www-ma2.upc.es\/egc15\/\" target=\"_blank\">XVI Spanish Meeting on Computational Geometry<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Seminars on Innovation and Research in Informatics (MIRI) Specialization in Computer Graphics and Virtual Reality Departament de Matem\u00e0tica Aplicada II Facultat d\u2019Inform\u00e0tica de Barcelona Universitat Polit\u00e8cnica de Catalunya Goal Contents Resources Related events Goal This seminar is designed as an introduction to geometric algorithms. As the field is far too wide to fit in a&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":41,"menu_order":5,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-974","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/pages\/974","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/comments?post=974"}],"version-history":[{"count":24,"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/pages\/974\/revisions"}],"predecessor-version":[{"id":1020,"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/pages\/974\/revisions\/1020"}],"up":[{"embeddable":true,"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/pages\/41"}],"wp:attachment":[{"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/media?parent=974"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}