UNIVERSITAT POLITÈCNICA DE CATALUNYA
Barcelona, Catalonia, Spain
Departament de Matemàtica
Aplicada II
General report on members and activities
The area of research. Computational Geometry studies geometric problems from the viewpoint of computation, and is strongly connected to the field of Discrete and Combinatorial Geometry. An essential part of the core is the design and analysis of algorithms for the efficient solution of geometric problems. As a consequence, a fundamental task is identifying concepts, properties, and techniques which aid efficient algorithmic development. This leads to the analysis of the combinatorial complexity of geometric structures, the study of geometric data structures, the complexity of algorithms, the representation and manipulation of figures and objects, the construction of geometric loci, and, more in general, the development of suitable geometrical foundations. Some particular classes of problems addressed include geometric searching and retrieval, convexity and related topics, proximity, intersection, geometric decomposition, arrangements of geometric objects, shape approximation and visibility. The main areas of application are Computer Graphics, Computer Aided Design and Manufacture (CAD/CAM), Pattern Recognition, Computational Morphology, VLSI Design, Artificial Vision, Geographic Information and Robotics.
The Group. Research activities in Computational Geometry started at the UPC in the early nineties, with the work of Professors Hurtado, Noy, Serra and Trias. An official Group of Research was created in 1993, under the responsibility of Prof. F. Hurtado. An associated line on Computational Algebra was created in1998 under the responsability of Prof. A. Montes. Due to the background of many members of the group, the interface with Combinatorics and Graph Theory is an specially active area of research.
Ongoing research. Our research projects currently include Discrete geometry: problems on combinatorics and computation, ending by the end of 2012 (MEC/MICINN Research Project). General research is also funded by the Generalitat de Catalunya (Grup consolidat de recerca 2009-2013).
Subjects of main interest (general line)
Neither exhaustive nor disjoint, the next list gives an idea of the main
research subjects in the Group.
Geometric graphs. In the largest sense, a geometric graph is one that conveys geometric information, so nodes or edges have some geometric meaning, and the combinatorial properties depend on it. Proximity graphs, visibility graphs, rotation-triangulation graphs, geometric-tree graphs, besides Graph Drawing problems are examples of specific topics.
Morphology. To extract "the shape" of a geometric object
or arrangement using algorithms and operators from Computational Geometry
is the main concern of Computational Morphology. The complexity and efficiency
of the methods is then naturally related to the complexity of the given shape.
Simplification by inscription or enclosure, quality of sections/projections,
reconstruction of objects (or properties), are some of the items the Group
has studied.
Visibility. Problems on visibility play a fundamental role in many applications of Computational Geometry (Robotics and Computer Graphics). The information is usually stored in a graph or in a cellular complex. Fundamental problems arise then on the relation between the characteristics of these structures and the geometric properties of the objects. The Goup has been working, for example, in Art Gallery problems, hybrid problems in which there is metric additional information, visibility graph properties, and in applications to Computer Graphics such as precomputation for radiosity.
Combinatorial complexity. From enumeration to characterization, the combinatorial structure of geometric problems can often decide which algorithmic approach could solve the problem efficiently, and will also appear in the analysis of the methods. Many fundamental problems appear in this area. We have been interested here mostly on several enumerative problems, but also on the study of fundamental structures, such as order types or decompositions and partitions.
Triangulations. To decompose a geometric domain into smaller and simpler pieces is a first step in many procedures, and triangulating (in general decomposition into simplices) is by far the most useful and common approach. The study of these structures, and especially how the different triangulations a domain admits are related, is a subject of continued research activity in the Group.
Modular reconfiguration. Versatility of self-reconfiguring modular robots makes them a promising area in Robotics. Obtaining efficient –centralized and distributed, global and local, sequential and parallel– reconfiguration algorithms for these robots, as well as general results on reconfiguration feasibility, is an active field of research of the Group.
Polytopes, graphs and combinatorics.
Convex polytopes are fascinating objects lying at the cross-roads
of algebra, combinatorics and geometry. On the one hand, there are many
tantalizing questions about their structure and behavior that we would
love to answer; on the other, they provide the scene on which a rich
interplay between graphs, lattices, and polynomials unfolds.
Illuminating the connections between these different fields has long
been a driving force behind the group's research effort.
Subline on Computational Algebra
Computer Algebra is the study of polynomial systems of equations in several variables. It formulate questions about the finiteness of the number of solutions, or how to compute and describe them. The solutions constitute an algebraic variety. The geometrical object corresponding to a variety is an ideal. There exist a close relationship between ideals and varieties revealing the intimate link between Algebra and Geometry, caracterized by Hilbert Nullstellensatz. Theory and algorithms answering such questions were discovered in the 1960's, even if there exists deep historical roots. The research field has started with Buchberger's work introducing the Groebner basis, which allow some kind of division in polynomial rings.
Computational aspects have fastly grown in recent years. The new algorithms have lead to some interessting applications, for example, in robotics and automatic theorem proving, and more recently in Computational Geometry. Our group has developped also applications to electrical networks.
RESPONSIBLE/CONTACT PERSON:
A picture including several of us is here.
Courses, Seminars, Conferences, Workshops
The Group supports courses in the Doctoral Program Applied Mathematics (inf. in catalan) of the Universitat Politècnica de Catalunya. Attached to the Program there is also a weekly Seminar on Computational Geometry. The Seminar is also the forum for talks given by visitors.
The Group has organized several conferences, workshops and courses:
Collaboration with other groups. Visitors
In the last years a collaboration has been developed with the following groups:
Arrival and departure: You will find here a few hints about the airport, the railroad station and how to get from there to the city.
Getting around: Here you have some information about how to get around within the city (bus, subway, city map,...) and outside the city (taking a train, renting a car,...). Includes directions to our Department.
Accomodation (not ready yet)
Sightseeing and more:
This is our particular and subjective suggestions about what to see, where
to eat, and more.
Ph D Position at UPC in Discrete/Combinatorial/Computational Geometry, January 2010
At the Department of Applied
Mathematics II of Universitat Politecnica de Catalunya (UPC),
Barcelona, Spain, there will very soon be an opening for a PhD student
in the aforementioned topics as part of a
project entitled “Discrete geometry:
problems on combinatorics and computation”, funded by the Spanish
"Ministerio de Ciencia e Innovacion" (MICINN) inside the program for
young researchers FPI2010.
The
MICINN call has not been launched yet, but it should happen by the
beginning of January, with an application deadline about 20 days later.
The outcome is expected to be known in about 6 months, and
the position be started by September 2010 (with some flexibility), for a period of 4 years.
Candidates
should have finished their degree when the grant starts and have a good
background in mathematics and/or computer science, ideally being strong
in discrete mathematics.
The research subject can range among a variety of topics. Interested
candidates are strongly advised to contact their potential supervisors
now:
(a) Dr. Julian Pfeifle offers several PhD projects in discrete
geometry, ranging from specific questions in (lattice) polytope theory
to connections with neighboring areas in geometry, graph theory
and combinatorics. More details are available on
request.
julian<DOT>pfeifle<AT>upc<dot>edu
http://www-ma2.upc.edu/~julian/
(b) Dr. Carlos Seara offers to supervise a research focusing on
algorithmic issues on the study of classifiers/discriminators
with low complexities for clases of colored objects in two and three
dimensions, as well as related discrepancy
problems.
carlos<DOT>seara<AT>upc<dot>edu
http://www-ma2.upc.edu/seara/
(c) Other members of the group might consider a Ph D supervision but
should be contacted before submitting any applications. Some
information on the group can be found in this page
(http://www-ma2.upc.es/~geomc/gcwww.html)
More details about the similar call last year can be found in the web of the Ministry (the information is in Spanish):
FPI 2009
(http://web.micinn.es/contenido.asp?menu1=1&menu2=&menu3=&dir=03_Plan_IDI/00-LIAs/00@LIARRHH/00-Formacion/00-FPI/001Con09)
BOE 2009-01-05
(http://www.boe.es/boe/dias/2009/01/05/pdfs/BOE-A-2009-172.pdf)
