This book contains a collection of articles corresponding to some of the talks delivered at the Foundations of Computational Mathematics conference held at IMPA in Rio de Janeiro in January 1997. Some ofthe others are published in the December 1996 issue of the Journal of Complexity. Both of these publications were available and distributed at the meeting. Even in this aspect we hope to have achieved a synthesis of the mathematics and computer science cultures as well as of the disciplines. The reaction to the Park City meeting on Mathematics of Numerical Analy sis: Real Number Algorithms which was chaired by Steve Smale and had around 275 participants, was very enthusiastic. At the suggestion of Narendra Karmar mar a lunch time meeting of Felipe Cucker, Arieh Iserles, Narendra Karmarkar, Jim Renegar, Mike Shub and Steve Smale decided to try to hold a periodic meeting entitled "Foundations of Computational Mathematics" and to form an organization with the same name whose primary purpose will be to hold the meeting. This is then the first edition of FoCM as such. It has been organized around a small collection of workshops, namely - Systems of algebraic equations and computational algebraic geometry - Homotopy methods and real machines - Information-based complexity - Numerical linear algebra - Approximation and PDEs - Optimization - Differential equations and dynamical systems - Relations to computer science - Vision and related computational tools There were also twelve plenary speakers."

This is the softcover reprint of the 1974 English translation of the later chapters of Bourbaki 's Topologie Generale. Initial chapters study subgroups and quotients of R, real vector spaces and projective spaces, and additive groups Rn. Analogous properties are then studied for complex numbers. Later chapters illustrate the use of real numbers in general topology and discuss various topologies of function spaces and approximation of functions.

This is the softcover reprint of the English translation of 1971 (available from Springer since 1989) of the first 4 chapters of Bourbaki's Topologie générale. It gives all the basics of the subject, starting from definitions. Important classes of topological spaces are studied, uniform structures are introduced and applied to topological groups. Real numbers are constructed and their properties established. Part II, comprising the later chapters, Ch. 5-10, is also available in English in softcover.

The book introduces conceptually simple geometric ideas based on the existence of fundamental domains for metric G- spaces. A list of the problems discussed includes Borsuk-Ulam type theorems for degrees of equivariant maps in finite and infinite dimensional cases, extensions of equivariant maps and equivariant homotopy classification, genus and G-category, elliptic boundary value problem, equivalence of p-group representations.
The new results and geometric clarification of several known theorems presented here will make it interesting and useful for specialists in equivariant topology and its applications to non-linear analysis and representation theory.

This anthology is based on the First ACM Workshop on Applied Computational Geometry, WACG '96, held in Philadelphia, PA, USA, in May 1996, as part of the FCRC Conference.
Today, CG is in transition and applied computational geometry has established itself as a fertile meeting ground for theorists from core computational geometry and practitioners from the potential application areas to exchange their ideas and identify issues of common interest. The book presents 11 invited contributions and state-of-the-art reports by leading experts together with 12 refereed full papers selected from 32 submissions. It points the way towards geometrical engineering and addresses researchers and professionals sharing an interest in geometric algorithms and techniques and their use in computational sciences and engineering.

Convex and discrete geometry is one of the most intuitive subjects in mathematics. One can explain many of its problems, even the most difficult - such as the sphere-packing problem (what is the densest possible arrangement of spheres in an n-dimensional space?) and the Borsuk problem (is it possible to partition any bounded set in an n-dimensional space into n+1 subsets, each of which is strictly smaller in "extent" than the full set?) - in terms that a layman can understand; and one can reasonably make conjectures about their solutions with little training in mathematics.

This is a new in paperback version of a very successful monograph first published in 1980. The book presents a survey of the geometric quantization theory of Konstant and Souriau. For this new paperback edition the text has been extensively rewritten and brought up-to-date, with the addition of many new examples, and an expansion of the material on field theory.

In this book, two seemingly unrelated fields -- algebraic topology and robust control -- are brought together. The book develops algebraic/differential topology from an application-oriented point of view. The book takes the reader on a path starting from a well-motivated robust stability problem, showing the relevance of the simplicial approximation theorem and how it can be efficiently implemented using computational geometry. The simplicial approximation theorem serves as a primer to more serious topological issues such as the obstruction to extending the Nyquist map, K-theory of robust stabilization, and eventually the differential topology of the Nyquist map, culminating in the explanation of the lack of continuity of the stability margin relative to rounding errors. The book is suitable for graduate students in engineering and/or applied mathematics, academic researchers and governmental laboratories.

This book constitutes the refereed proceedings of the 6th International Workshop on Discrete Geometry for Computer Imagery, DGCI'96, held in Lyon, France, in November 1996.
Computer imaging essentially depends on discrete models for coding, processing, recognition, representation, etc. The volume presents 24 revised full papers selected from 41 submissions together with 3 invited contributions and a tutorial paper, which bridges the gap between theory and practice. The issues addressed are topology, geometry, shape representation, 3D surfaces and volumes, models for discrete space, image transformation and generation.

This book introduces the graduate mathematician and researcher to the effective use of nonstandard analysis (NSA). It provides a tutorial introduction to this modern theory of infinitesimals, followed by nine examples of applications, including complex analysis, stochastic differential equations, differential geometry, topology, probability, integration, and asymptotics. It ends with remarks on teaching with infinitesimals.

This book has been called a Workbook to make it clear from the start that it is not a conventional textbook. Conventional textbooks proceed by giving in each section or chapter first the definitions of the terms to be used, the concepts they are to work with, then some theorems involving these terms (complete with proofs) and finally some examples and exercises to test the readers' understanding of the definitions and the theorems. Readers of this book will indeed find all the conventional constituents--definitions, theorems, proofs, examples and exercises but not in the conventional arrangement. In the first part of the book will be found a quick review of the basic definitions of general topology interspersed with a large num ber of exercises, some of which are also described as theorems. (The use of the word Theorem is not intended as an indication of difficulty but of importance and usefulness. ) The exercises are deliberately not "graded"-after all the problems we meet in mathematical "real life" do not come in order of difficulty; some of them are very simple illustrative examples; others are in the nature of tutorial problems for a conven tional course, while others are quite difficult results. No solutions of the exercises, no proofs of the theorems are included in the first part of the book-this is a Workbook and readers are invited to try their hand at solving the problems and proving the theorems for themselves."

This book is devoted to the development of adequate spatial representations for robot motion planning. Drawing upon advanced heuristic techniques from AI and computational geometry, the authors introduce a general model for spatial representation of physical objects. This model is then applied to two key problems in intelligent robotics: collision detection and motion planning. In addition, the application to actual robot arms is kept always in mind, instead of dealing with simplified models.
This monograph is built upon Angel del Pobil's PhD thesis which was selected as the winner of the 1992 Award of the Spanish Royal Academy of Doctors.

The book discusses various construction principles for translation planes and spreads from a general and unifying point of view and relates them to the theory of kinematic spaces. The book is intended for people working in the field of incidence geometry and can be read by everyone who knows the basic facts about projective and affine planes.
The methods developed work especially well for topological spreads of real and complex vector spaces. In particular, a complete classification of all semifield spreads of finite dimensional complex vector spaces is obtained.

Singular spaces with upper curvature bounds and, in particular, spaces of nonpositive curvature, have been of interest in many fields, including geometric (and combinatorial) group theory, topology, dynamical systems and probability theory. In the first two chapters of the book, a concise introduction into these spaces is given, culminating in the Hadamard-Cartan theorem and the discussion of the ideal boundary at infinity for simply connected complete spaces of nonpositive curvature. In the third chapter, qualitative properties of the geodesic flow on geodesically complete spaces of nonpositive curvature are discussed, as are random walks on groups of isometries of nonpositively curved spaces. The main class of spaces considered should be precisely complementary to symmetric spaces of higher rank and Euclidean buildings of dimension at least two (Rank Rigidity conjecture). In the smooth case, this is known and is the content of the Rank Rigidity theorem. An updated version of the proof of the latter theorem (in the smooth case) is presented in Chapter IV of the book. This chapter contains also a short introduction into the geometry of the unit tangent bundle of a Riemannian manifold and the basic facts about the geodesic flow. In an appendix by Misha Brin, a self-contained and short proof of the ergodicity of the geodesic flow of a compact Riemannian manifold of negative curvature is given. The proof is elementary and should be accessible to the non-specialist. Some of the essential features and problems of the ergodic theory of smooth dynamical systems are discussed, and the appendix can serve as an introduction into this theory.

This introduction to modern geometry differs from other books in the field due to its emphasis on applications and its discussion of special relativity as a major example of a non-Euclidean geometry. Additionally, it covers the two important areas of non-Euclidean geometry, spherical geometry and projective geometry, as well as emphasising transformations, and conics and planetary orbits. Much emphasis is placed on applications throughout the book, which motivate the topics, and many additional applications are given in the exercises. It makes an excellent introduction for those who need to know how geometry is used in addition to its formal theory.

The book collects results about realization spaces of polytopes. It gives a presentation of the author's "Universality Theorem for 4-polytopes." It is a comprehensive survey of the important results that have been obtained in that direction. The approaches chosen are direct and very geometric in nature. The book is addressed to researchers and to graduate students. The former will find a comprehensive source for the above mentioned results. The latter will find a readable introduction to the field. The reader is assumed to be familiar with basic concepts of linear algebra.

In this broad introduction to topology, the author searches for topological invariants of spaces, together with techniques for calculating them. Students with knowledge of real analysis, elementary group theory, and linear algebra will quickly become familiar with a wide variety of techniques and applications involving point-set, geometric, and algebraic topology. Over 139 illustrations and more than 350 problems of various difficulties will help students gain a rounded understanding of the subject.

Geometry undoubtedly plays a central role in modern mathematics. And it is not only a physiological fact that 80 % of the information obtained by a human is absorbed through the eyes. It is easier to grasp mathematical con- cepts and ideas visually than merely to read written symbols and formulae. Without a clear geometric perception of an analytical mathematical problem our intuitive understanding is restricted, while a geometric interpretation points us towards ways of investigation. Minkowski's convexity theory (including support functions, mixed volu- mes, finite-dimensional normed spaces etc.) was considered by several mathe- maticians to be an excellent and elegant, but useless mathematical device. Nearly a century later, geometric convexity became one of the major tools of modern applied mathematics. Researchers in functional analysis, mathe- matical economics, optimization, game theory and many other branches of our field try to gain a clear geometric idea, before they start to work with formulae, integrals, inequalities and so on. For examples in this direction, we refer to [MalJ and [B-M 2J. Combinatorial geometry emerged this century. Its major lines of investi- gation, results and methods were developed in the last decades, based on seminal contributions by O. Helly, K. Borsuk, P. Erdos, H. Hadwiger, L. Fe- jes T6th, V. Klee, B. Griinbaum and many other excellent mathematicians.

Experts from university and industry are presenting new technologies for solving industrial problems and giving many important and practicable impulses for new research. Topics explored include NURBS, product engineering, object oriented modelling, solid modelling, surface interrogation, feature modelling, variational design, scattered data algorithms, geometry processing, blending methods, smoothing and fairing algorithms, spline conversion. This collection of 24 articles gives a state-of-the-art survey of the relevant problems and issues in geometric modelling.

The purpose of this book is to provide an integrated development of modern analysis and topology through the integrating vehicle of uniform spaces. The reader should have taken an advanced calculus course and an introductory topology course. It is intended that a subset of the book could be used for an upper-level undergraduate course whereas much of the full text would be suitable for a one-year graduate class. An attempt has been made to document the history of all the central ideas and references and historical notes are embedded in the text. These can lead the interested reader to the foundational sources where these ideas emerged.

This book is a study of combinatorial structures of 3-mani- folds, especially Haken 3-manifolds. Specifically, it is concerned with Heegard graphs in Haken 3-manifolds, i.e., with graphs whose complements have a free fundamental group. These graphs always exist. They fix not only a combinatorial stucture but also a presentation for the fundamental group of the underlying 3-manifold. The starting point of the book is the result that the intersection of Heegard graphs with incompressible surfaces, or hierarchies of such surfaces, is very rigid. A number of finiteness results lead up to a ri- gidity theorem for Heegard graphs. The book is intended for graduate students and researchers in low-dimensional topolo- gy as well as combinatorial theory. It is self-contained and requires only a basic knowledge of the theory of 3-manifolds

This book constitutes the refereed proceedings of the international Symposium on Graph Drawing, GD '95, held in Passau, Germany, in September 1995.
The 40 full papers and 12 system demonstrations were selected from a total of 88 submissions and include, in their revised versions presented here, the improvements suggested during the meeting. This book also contains a report on the graph-drawing contest held in conjunction with GD '95. Graph drawing is concerned with the problem of visualizing structural information, particularly by constructing geometric representations of abstract graphs and networks. The importance of this area for industrial applications is testified by the large number of people with industrial affiliations, submitting papers and participating in the meeting.

This monograph is devoted to computational morphology, particularly to the construction of a two-dimensional or a three-dimensional closed object boundary through a set of points in arbitrary position.
By applying techniques from computational geometry and CAGD, new results are developed in four stages of the construction process: (a) the gamma-neighborhood graph for describing the structure of a set of points; (b) an algorithm for constructing a polygonal or polyhedral boundary (based on (a)); (c) the flintstone scheme as a hierarchy for polygonal and polyhedral approximation and localization; (d) and a Bezier-triangle based scheme for the construction of a smooth piecewise cubic boundary.

This volume is an introduction and a monograph about tight polyhedra. The treatment of the 2-dimensional case is self- contained and fairly elementary. It would be suitable also for undergraduate seminars. Particular emphasis is given to the interplay of various special disciplines, such as geometry, elementary topology, combinatorics and convex polytopes in a way not found in other books. A typical result relates tight submanifolds to combinatorial properties of their convex hulls. The chapters on higher dimensions generalize the 2-dimensional case using concepts from combinatorics and topology, such as combinatorial Morse theory. A number of open problems is discussed.

Topological Methods for Differential Equations and Inclusions covers the important topics involving topological methods in the theory of systems of differential equations. The equivalence between a control system and the corresponding differential inclusion is the central idea used to prove existence theorems in optimal control theory. Since the dynamics of economic, social, and biological systems are multi-valued, differential inclusions serve as natural models in macro systems with hysteresis.