{"id":359,"date":"2012-10-29T15:52:55","date_gmt":"2012-10-29T14:52:55","guid":{"rendered":"http:\/\/www-ma2.upc.es\/vera\/?page_id=359"},"modified":"2020-08-31T12:11:20","modified_gmt":"2020-08-31T11:11:20","slug":"discrete-and-algorithmic-geometry","status":"publish","type":"page","link":"https:\/\/dccg.upc.edu\/people\/vera\/teaching\/courses\/discrete-and-algorithmic-geometry\/","title":{"rendered":"Discrete and Algorithmic Geometry-MAMME"},"content":{"rendered":"\n<p><p><strong>Master in&nbsp;Advanced Mathematics and Mathematical Engineering (MAMME)<\/strong><br>Departament de Matem\u00e0rica Aplicada II<br>Facultat de Matem\u00e0tiques i Estad\u00edstica<br>Universitat Polit\u00e8cnica de Catalunya<\/p><p> <\/p><\/p>\n\n\n\n<p class=\"has-text-align-center has-black-color has-pale-pink-background-color has-text-color has-background has-normal-font-size\"><strong>Warning! <\/strong><br>Since I retired in August 2020, this page is obsolete. The updated page for this course can be found here: <a href=\"https:\/\/dccg.upc.edu\/courses-dag\/\">https:\/\/dccg.upc.edu\/courses-dag\/<\/a><\/p>\n\n\n<p><a href=\"https:\/\/fme-intranet.upc.edu\/tmp\/consgd\/cursactual\/34956-e-3.pdf\" target=\"_blank\" rel=\"noopener noreferrer\">General information<\/a>&nbsp;on the course (syllabus, references, evaluation, etc.).<br><a href=\"http:\/\/mamme.masters.upc.edu\/en\/current-academic-year-information\" target=\"_blank\" rel=\"noopener noreferrer\">Particular information<\/a> on the course for the current term (teaching hours, classroom, calendar, etc.)<\/p>\n<hr>\n<h3>Some material for the course<\/h3>\n<ol>\n<li>Background\n<ul>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-AnalyzingAlgorithms.pdf\">Analyzing algorithms<\/a><\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-UsingAppropriateDataStructure.pdf\">Using the appropriate data structure<\/a><\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Geometric-objects.pdf\">Describing and implementing basic geometric objects<\/a><\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/median-finding.pdf\">Median finding<\/a><\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/MasterTheorem.pdf\">Complexity of recursive algorithms<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Basic tool: <a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-OrientationTests.pdf\">orientation tests<\/a><\/li>\n<li>Intersecting line segments: <a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-IntersectingSegments.pdf\">Bentley-Ottman&#8217;s algorithm<\/a><\/li>\n<li>Computing the convex hull of a finite point set\n<ul>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Convex-Hull-2D.pdf\">Convex hulls in 2D<\/a><\/li>\n<li>Convex hull of a simple polygon: <a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/Example-CH-polygon.pdf\">a curiosity<\/a><\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Convex-Hull-3D.pdf\">Convex hulls in 3D<\/a><\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Convex-Hull-dD.pdf\">Convex hulls in higher dimensions<\/a><\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-IntersectingHalfplanes.pdf\">Intersecting half-planes and related problems<\/a>: duality, computing the intersection of half-planes, solving linear programs, and computing the minimum spanning circle of a set of points.\n<ul>\n<li>An <a href=\"https:\/\/dccg.upc.edu\/people\/vera\/teaching\/courses\/discrete-and-algorithmic-geometry\/the-parabola-and-the-circle-dualities-applet\/\" target=\"_blank\" rel=\"noopener noreferrer\">applet<\/a> for visualizing dualities in the plane.<\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/median-finding.pdf\">Median finding<\/a><\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-TriangulatingPolygons.pdf\">Triangulating polygons<\/a><\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/TriangulatingPoints.pdf\">Triangulating point sets: introduction<\/a><\/li>\n<li>Proximity\n<ul>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Voronoi_1_Proximity.pdf\">Proximity problems, Voronoi diagrams, properties<\/a><\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/Voronoi_2_Storing.pdf\">Storing a Voronoi diagram<\/a><\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Voronoi_3_Computing.pdf\">Computing a Voronoi diagram<\/a><\/li>\n<li>Applet: <a href=\"https:\/\/dccg.upc.edu\/people\/vera\/teaching\/courses\/discrete-and-algorithmic-geometry\/applet-the-farthest-point-voronoi-diagram\/\" target=\"_blank\" rel=\"noopener noreferrer\">the farthest point Voronoi diagram<\/a><\/li>\n<\/ul>\n<\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Delaunay.pdf\">Triangulating point sets: the Delaunay triangulation<\/a><\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-PointLocation.pdf\">Point location in planar subdivisions<\/a><\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/Arrangements-Modified-Ipe7.pdf\">Arrangements of lines<\/a><\/li>\n<li>Robustness in geometric computations:\n<ul>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-RobustnessAndCGAL.pdf\" rel=\"\">Robustness and CGAL<\/a>, by Rodrigo Silveira<\/li>\n<li><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-classroomExamplesNonrobustness.pdf\" rel=\"\">Classrom Examples of Robustness Problems in Geometric Computations<\/a>, by L. Kettner, K. Melhorn, S. Pion, S. Schirra and C. Yap.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<hr>\n<h3>Problems and assignments (year 2016-17)<\/h3>\n<p><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Pr1-2016-17.pdf\">Problems list 1<\/a><br>Problems to turn in: &#8212;<br>Deadline: &#8212;<\/p>\n<p><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Pr2-2016-17.pdf\">Problems list 2<\/a><br>Problems to turn in: 2 and 8<br>Deadline: Monday, October 10<\/p>\n<p><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Pr3-2016-17.pdf\">Problems list 3<\/a><br>Problems to turn in: 1 and 7<br>Deadline: Monday, October 17<\/p>\n<p><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Pr4-2016-17.pdf\">Problems list 4<\/a><br>Problems to turn in: 1 and 11<br>Deadline: Friday, October 28<\/p>\n<p><a href=\"https:\/\/dccg.upc.edu\/people\/vera\/wp-content\/uploads\/2012\/10\/DAG-Pr5-2016-17.pdf\">Problems list 5<\/a><br>Problems to turn in: 9 and 16<br>Deadline: Monday, November 7<\/p>\n<hr>\n<h3>References<\/h3>\n<ul>\n<li>Berg, Mark de; Cheong, Otfried; Kreveld, Marc van; Overmars, Mark. <a href=\"http:\/\/cataleg.upc.edu\/record=b1326857\" target=\"_blank\" rel=\"noopener noreferrer\"><em>Computational geometry: algorithms and applications<\/em><\/a>. 3rd ed. revised. Berlin: Springer, 2008. ISBN 9783540779735.<\/li>\n<li>Boissonnat, J. D.; Yvinec, M. <a href=\"http:\/\/cataleg.upc.edu\/record=b1137324\" target=\"_blank\" rel=\"noopener noreferrer\"><em>Algorithmic Geometry<\/em><\/a>. Cambridge: Cambridge University Press, 1997. ISBN 0521565294.<\/li>\n<li>Edelsbrunner, Herbert. <a href=\"http:\/\/cataleg.upc.edu\/record=b1024045\" target=\"_blank\" rel=\"noopener noreferrer\"><em>Algorithms in combinatorial geometry<\/em><\/a>. Berl\u00edn: Springer, 1987. ISBN 354013722X.<\/li>\n<\/ul>\n<p>Please see the official <a href=\"https:\/\/fme-intranet.upc.edu\/tmp\/consgd\/cursactual\/34956-e-3.pdf\" target=\"_blank\" rel=\"noopener noreferrer\">general information<\/a> for this course for more information.<\/p>\n<hr>\n<h3>Further resources<\/h3>\n<ul>\n<li>Mathematical text editor<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">Mathematical edition is almost always and everywhere done using LaTeX. Not only it is used in universities (LaTeX has been used to write all the documents of this course, and probably all the problems lists, exams, and other mathematical texts that you had in your hands during your previous studies) but it 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).<\/p>\n<p style=\"padding-left: 30px;\">It&#8217;s a free source software that has versions for all operating systems (Linux, Mac, Windoxs, etc.), it helps writing all sort of scientific texts, such as articles, books and presentations, while it allows to incorporate figures previously produced in PDF by any drawing program.<\/p>\n<p style=\"padding-left: 30px;\">You can download LaTeX from <a href=\"http:\/\/www.tug.org\/\" target=\"_blank\" rel=\"noopener noreferrer\">http:\/\/www.tug.org\/<\/a><\/p>\n<p style=\"padding-left: 30px;\">References:<\/p>\n<ul>\n<li style=\"list-style-type: none;\">\n<ul>\n<li>Introductory text: L. Lamport, <em><a href=\"http:\/\/cataleg.upc.edu\/record=b1097622\" target=\"_blank\" rel=\"noopener noreferrer\">LaTeX, a Document Preparation System<\/a><\/em>, Addison-Wesley, 2nd ed., 1994.<\/li>\n<li><a href=\"http:\/\/www.latex-project.org\/\" target=\"_blank\" rel=\"noopener noreferrer\">The LaTeX project site<\/a>.<\/li>\n<li><a href=\"http:\/\/en.wikibooks.org\/wiki\/LaTeX\" target=\"_blank\" rel=\"noopener noreferrer\">The LaTeX wikibook<\/a>.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">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\" rel=\"noopener noreferrer\">http:\/\/www.winedt.com\/<\/a><\/p>\n<ul>\n<li>Drawings<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">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. It&#8217;s a free source software that has versions for all the operating systems (Linux, Windoxs, Unix, etc.).<\/p>\n<p style=\"padding-left: 30px;\">You can download IPE from <a href=\"http:\/\/ipe.otfried.org\/\" target=\"_blank\" rel=\"noopener noreferrer\">http:\/\/ipe.otfried.org\/<\/a><\/p>\n<ul>\n<li>Geometric constructions<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">In addition to producing your own drawings, you may wish to create and experiment with geometric constructions. If so, I recommend GeoGebra: <a href=\"http:\/\/www.geogebra.org\/cms\/\" target=\"_blank\" rel=\"noopener noreferrer\">http:\/\/www.geogebra.org\/cms\/<\/a><\/p>\n<hr>\n<h3>Thesis, grants and projects<\/h3>\n<ul>\n<li>Are you interested in doing your Masther Thesis in Computational Geometry? <a href=\"https:\/\/dccg.upc.edu\/people\/vera\/teaching\/tesis-de-grau-i-de-master-i-projectes-fi-de-carrera\/\">Have a look!<\/a><\/li>\n<li>Are you interested in working in a Computational Geometry project? <a href=\"https:\/\/dccg.upc.edu\/people\/vera\/teaching\/grants-beques\/\">Have a look!<\/a><\/li>\n<li>Are you interested in doing your PhD in Computational Geometry? <a href=\"https:\/\/dccg.upc.edu\/people\/vera\/research\/beques-doctorals\/\">Have a look!<\/a><\/li>\n<li>Do you want to know what our Research Gropu does? <a href=\"https:\/\/dccg.upc.edu\/\" target=\"_blank\" rel=\"noopener noreferrer\">Look here!<\/a><\/li>\n<\/ul>","protected":false},"excerpt":{"rendered":"<p>Master in&nbsp;Advanced Mathematics and Mathematical Engineering (MAMME)Departament de Matem\u00e0rica Aplicada IIFacultat de Matem\u00e0tiques i Estad\u00edsticaUniversitat Polit\u00e8cnica de Catalunya Warning! Since I retired in August 2020, this page is obsolete. The updated page for this course can be found here: https:\/\/dccg.upc.edu\/courses-dag\/ General information&nbsp;on the course (syllabus, references, evaluation, etc.).Particular information on the course for the current&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":41,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-359","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/pages\/359","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=359"}],"version-history":[{"count":144,"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/pages\/359\/revisions"}],"predecessor-version":[{"id":1820,"href":"https:\/\/dccg.upc.edu\/people\/vera\/wp-json\/wp\/v2\/pages\/359\/revisions\/1820"}],"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=359"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}