# Computational geometry (2008/2009)

### Course Not running, not visible

Course code
4S00246
Credits
5
Coordinator
Andrea Fusiello
Teaching is organised as follows:
modulo base 3 MAT/03-GEOMETRY 1° Q Mauro Spera
modulo avanzato 2 MAT/03-GEOMETRY 1° Q Andrea Fusiello

#### Learning outcomes

Module: modulo base
-------
The course consists in an introduction to projective geometry, steered towards
the applications to vision and drawing problems, via a hybrid appoach: analytic (via coordinates and matrices), and synthetic.

Module: modulo avanzato
-------
This module aims at illustrating the foundations of computational geometry, describing its main problems and algorithms.

#### Syllabus

Module: modulo base
-------
Computational GEOMETRY (basic module): Syllabus (tentative).
The course consists in an introduction to projective geometry, steered towards
the applications to vision and drawing problems, via a hybrid appoach: analytic (via coordinates and matrices), and synthetic.
Historical introduction. Review of projective spaces and their transformations (generalities),
and conics (polarity) (analytical approach). Pencils of conics. Affine and metric classification
of conics. Quadrics and their projective, affine and metric classification. Synthetic approach to projective geometry: projections and sections. Desargues' theorem on homological triangles. Collineations (homographies, projectivities) between ranges and pencils. Axis of collineation (perspective). Pappus' theorem. Cross ratio. Harmonic ranges. Involutions. The theorems of Menelaus and Ceva. Desargues' theorem on the complete quadrangle. Plane homographies. Homologies. Desargues' theorem revisited. Application to perspective drawing.
Matrix approach to plane and spatial homographies. The viewing pipeline. Applications to computer vision: camera calibration, affine and metric reconstruction of images, via the absolute conic. The calibrating conic.
Further elements in the theory of conics: projective generation (Steiner-Chasles),
the four point and four tangent theorems, Pascal's and Brianchon's theorems, the Desargues-Sturm theorem. Conics as (rational) Bézier curves.
Epipolar geometry. Kruppa's equations.

Appendix: review of some linear algebra techniques: SVD, QR (and RQ), Choleski (for symmetric positive definite matrices), pseudoinverse. Sylvester's inertia theorem and the spectral theorem.

(revised version), and posted on line (course web page.
2. The program is tentative and subject to change.

References

M.SPERA ,Appunti delle lezioni (note manoscritte)

Lezioni di geometria analitica e proiettiva, Bollati-Boringhieri, Torino, 2002.

R.CASSE, Projective Geometry, an introduction Oxford University Press,
Oxford, 2006

L.CATASTINI, F.GHIONE, Le Geometrie della Visione, Springer, Milano, 2003.

G.CASTELNUOVO, Lezioni di Geometria Analitica , Soc. Ed. Dante Alighieri, Milano, Roma, 1969.

M.DOCCI, R.MIGLIARI, La Scienza della rappresentazione.
Fondamenti e applicazioni della geometria descrittiva, Carocci, Roma, 1999.

F.ENRIQUES, Lezioni di Geometria Proiettiva, Zanichelli, Bologna, 1996.

G.FARIN, NURBS- From Porjective Geometry to practical use, AK Peters, Natick, MA, 1999.

G.FARIN, Curves and Surfaces for CAGD. A practical guide, Academic Press, London, 2002.

J.GALLIER, Geometric Methods and Applications for Computer Science and
Engineering, Springer, Berlin, 2000.

R.HARTLEY, A.ZISSERMAN, Multiple View Geometry in Computer Vision,
Cambridge, Cambridge, 2003.

D.HILBERT, S.COHN-VOSSEN Geometria intuitiva, Boringhieri, Torino, 1972.

D.MARSH, Applied Geometry for Computer Graphics and CAD,
Springer, London, 2005.

M.E.MORTENSON, Modelli geometrici in computer graphics, McGraw-Hill Libri Italia, Milano, 1989.

E.SERNESI, Geometria 1,2 Bollati Boringhieri, Torino, 1989, 1994.

J.C. SIDLER, Ge'ome'trie projective, Dunod, Paris, 2000.

A.WATT, 3D Computer Graphics, Addison-Wesley (Pearson Education), Harlow, 2000.

Module: modulo avanzato
-------
* Introduction
* Background material
* Polygon triangulation
* Convex hull
* Intersections
* Plane subdivision
* Geometric search
* Proximity (Voroni diagrams, Delaunay triangulation)

#### Assessment methods and criteria

Module: modulo base
-------
Assessment: Written exam at the end of the course, followed by an oral test (to be arranged with Prof. A.Fusiello, instructor of the advanced module).

Module: modulo avanzato
-------
Written exam at the end of the course, followed by an oral test.