National University of Athens Dept. of Informatics & Telecommunications Mini Workshop on Algebraic & Geometric Algorithms Wedn. 26/11, Room ST

Program
 

Bernard Mourrain: Symbolic numeric algebra for geometric problems.
In this talk, we will present several methods combining symbolic and numeric computation,  to deal with algebraic numbers, to solve polynomial equations, to compute the topology or arrangement of curve arcs, and surface patches. We will illustrate these technics by some experiments on conrete problems and discuss related implementation aspects.

Monique Teillaud: Sweeping an arrangement of quadrics.
We study here a sweeping algorithm to compute effectively the arrangement of a set of quadrics in 3D. The algorithm is described, and we show how and why we compute in fact the so called vertical decomposition of the arrangement. Combinatorial aspects are quickly studied, and algebraic aspects are discussed more precisely.
Joint work with Bernard Mourrain and Jean-Pierre Técourt.

Sylvain Pion: Fast and guaranteed arithmetic.
We will describe some interactions between geometric algorithms and the underlying arithmetic.  Then we will focus on some of the traditionnal arithmetic tools like multiprecision computations for integers and rationals, interval arithmetic and various kinds of fast arithmetic filters.

Michael N. Vrahatis: The Topological Degree and Its Computation.
Numerous problems in different areas of science and technology can be reduced to the study of the set of solutions of a system of nonlinear algebraic and/or transcendental equations. Topological degree theory has been developed as a means of examining this solution set and obtaining information concerning the existence of solutions, their number, and their nature. Furthermore, several applications involve the use of various fixed point theorems which can be provided by means of topological degree. We give a background on topological degree and we present efficient methods for computing its value.

Ioannis Z. Emiris : Algebraic methods for geometric predicates.
A major modern direction of Computational Geometry is the study of curved objects, thus extending traditional methods, including those for computing arrangements, Voronoi diagrams and convex hulls, to non-linear settings. This requires certain algebraic operations in order to implement the corresponding geometric tests. Our goal is exact, efficient and general computations with real algebraic numbers. This talk surveys the use, mainly, of Sturm sequences, but also resultants and Descartes' rule. They are illustrated by specific uses in solving geometric predicates. Parts of this work are joint with Menelaos Karavelas or Elias Tsigaridas.

Access: airport to city, city to Campus.
Organizer: Ioannis Z. Emiris.
Funding: Bilateral project "Calamata" between the GALAAD group of INRIA and the Lab of Geometric & Algebraic Algorithms.
Figure: Voronoi diagram of circles, by M. Karavelas.