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:
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.