T2 (14 a 17hs) Algoritmos Geométricos para Sistemas de Información Geográfica (GIS)

Profesor: Rodrigo Silveira (Universitat Politécnica de Catalunya, España). Horario: Turno tarde, de 14 a 17 horas. En castellano.

Profesor: Rodrigo Silveira

Horario: Lunes a viernes de 14 a 17 horas. Aula 8 (pabellón 1).

Idioma: castellano

Resumen:

La geometría computacional es un área muy activa de las ciencias de la computación que se dedica a estudiar problemas geométricos desde un punto de vista algorítmico. Su objetivo principal es diseñar y analizar algoritmos que involucran objetos geométricos (puntos, líneas, círculos, etc.), y que tienen aplicaciones en muchos y variados campos, como la computación gráfica, la robótica, o los sistemas de información geográfica. El énfasis de este curso estará puesto en este último. Los sistemas de información geográfica (GIS) son sistemas de software usados para almacenar, analizar y visualizar información espacial (es decir, información geográficamente referenciada). En este curso se presentarán algoritmos y estructuras de datos usados en geometría computacional que permiten diseñar algoritmos eficientes para GIS. El énfasis va a estar puesto en presentar y analizar algunos de los algoritmos geométricos más relevantes con aplicaciones a GIS. El curso tiene dos objetivos principales. Por un lado, brindar una introducción a la geometría computacional. Para esto veremos varias de sus herramientas más fundamentales (como los diagramas de Voronoi y estructuras de datos para point-location). Por otro lado, el curso intentará dar un pantallazo de los tipos de problemas algorítmicos que surgen al desarrollar un GIS, relacionados con la representación de terrenos y la cartografía digital, y que serán resueltos usando algoritmos geométricos.

Programa:

1. Introduction. Introduction to computational geometry. Basic geometric problems and algorithms. Introduction to geographical information systems (GIS). Examples of uses of a GIS. Role of computational geometry in GIS. Basic references: [6, 7].

2. Map overlay, point location and windowing. Line-segment intersection. Bentley– Ottmann’s algorithm. The point location problem. Trapezoidal maps. Windowing. Interval trees. Segment trees. Basic references: [3, 9].

3. Terrain modeling and analysis. Terrain representation: DEMs and TINs. Applications of terrain models. Triangulations. Delaunay triangulation. Optimization of triangulations. Data conﬂation for terrains. Embedding rivers in terrains. Basic references: [3, 10, 11].

4. Voronoi diagrams Main properties and algorithms. Applications to GIS. Fortune’s al- gorithm. Line-segment Voronoi diagrams. Other extensions and generalizations useful for GIS. Basic references: [1, 3, 4, 5].

5. Digital cartography. Map generalization. The road selection problem. Map labeling: area, point, and line labeling. Dynamic map labeling. Basic references: [2, 8, 12].

Bibliografía:

[1] F. Aurenhammer. Voronoi Diagrams—A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 23(3):345-405, 1991.

[2] K. Been, E. Daiches and C. Yap. Dynamic Map Labeling. IEEE Transactions on Visualization and Computer Graphics, 12(5): 773-780, 2006.

[3] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry, 3rd edition, Springer-Verlag, 2008.

[4] C. M. Gold. Applications of kinetic Voronoi diagrams. In Proc. 3rd Voronoi Conference on Analytic Number Theory and Space Tilings, pages 169-178, 2004.

[5] C. M. Gold, P. R. Remmele and T. Roos. Voronoi methods in GIS. In Algorithmic Foundations of Geographic Information Systems, pages 21–35 Springer Berlin / Heidelberg, 1997.

[6] I. Heywood, S. Cornelius and S. Carver. An Introduction to Geographical Information Systems, 3rd edition, Prentice Hall, 2006.

[7] F. Hurtado, Geometría computacional: una instantanea. Gaceta de la Real Sociedad Matemática Española. 2(2):371-380, 1999.

[8] Z. Li. Digital Map Generalization at the Age of Enlightenment: a Review of the First Forty Years. The Cartographic Journal, 44(1):80-93, 2007.

[9] J. Snoeyink. Point location. In Handbook of Discrete and Computational Geometry, 2nd edn, chapter 34, Chapman and Hall/CRC, 2004.

[10] M. van Kreveld, Digital elevation models and TIN algorithms. In Algorithmic Foundations of Geographic Information Systems, pages 37–78 Springer Berlin / Heidelberg, 1997.

[11] M. van Kreveld and R. I. Silveira, Embedding Rivers in Polyhedral Terrains. In Proc. 25th ACM Symposium on Computational Geometry, pages 169–178, ACM Press, 2009.

[12] A. Wolﬀ, L. Knipping, M. van Kreveld, T. Strijk and P. K. Agarwal. A Simple and Eﬃcient Algorithm for High-Quality Line Labeling. In Innovations in GIS VII: GeoComputation, Taylor & Francis, pages 147–159, 2000.