Mathematics

Handbook of Discrete and Computational Geometry, Second Edition edited by Jacob E. Goodman, Joseph O'Rourke (CRC Press) Comprehensive handbook for professionals in the field of Mathematics, Computer Science, and Computational Mathematics. A complete reference volume. The second edition of the Handbook of Discrete and Computational Geometry is a thoroughly revised version of the bestselling first edition. With the addition of 500 pages and 14 new chapters covering topics such as geometric graphs, collision detection, clustering, applications of computational geometry, and statistical applications, this is a significant update. This edition includes expanded coverage on the topics of mesh generation in two and three dimensions, aspect graphs, center points, and probabilistic roadmap algorithms. It also features new results on solutions of the Kepler conjecture, and honeycomb conjecture, new bounds on K sets, and new results on face numbers of polytopes.

While books and journals of high quality have proliferated in discrete and computational geometry during recent years, there has been to date no single reference work fully accessible to the nonspecialist as well as to the specialist, covering all the major aspects of both fields. The Handbook of Discrete and Computational Geometry is intended to do exactly that: to make the most important results and methods in these areas of geometry readily accessible to those who use them in their everyday work, both in the academic world as researchers in mathematics and computer science—and in the professional world as practitioners in fields as diverse as operations research, molecular biology, and robotics.

A significant part of the growth that discrete mathematics as a whole has experienced in recent years has consisted of a substantial development in discrete geometry. This has been fueled partly by the advent of powerful computers and by the recent explosion of activity in the relatively young field of computational geometry. This synthesis between discrete and computational geometry, in which the methods and insights of each field have stimulated new understanding of the other, lies at the heart of this Handbook.

The phrase "discrete geometry," which at one time stood mainly for the areas of packing, covering, and tiling, has gradually grown to include in addition such areas as combinatorial geometry, convex polytopes, and arrangements of points, lines, planes, circles, and other geometric objects in the plane and in higher dimensions. Similarly, "computational geometry," which referred not long ago to simply the design and analysis of geometric algorithms, has in recent years broadened its scope, and now means the study of geometric problems from a computational point of view, including also computational convexity, computational topology, and questions involving the combinatorial complexity of arrangements and polyhedra. It is clear from this that there is now a significant overlap between these two fields, and in fact this overlap has become one of practice as well, as mathematicians and computer scientists have found themselves working on the same geometric problems and have forged successful collaborations as a result.

At the same time, a growing list of areas in which the results of this work are applicable has been developing. It includes areas as widely divergent as engineering, crystallography, computer-aided design, manufacturing, operations research, geographic information systems, robotics, error-correcting codes, tomography, geometric modeling, computer graphics, combinatorial optimization, computer vision, pattern recognition, and solid modeling.

With this in mind, it has become clear that a handbook encompassing the most important results of discrete and computational geometry would benefit not only the workers in these two fields, or in related areas such as combinatorics, graph theory, geometric probability, and real algebraic geometry, but also the users of this body of results, both industrial and academic. This Handbook is designed to fill that role. We believe it will prove an indispensable working tool both for researchers in geometry and geometric computing and for professionals who use geometric tools in their work.

The Handbook covers a broad range of topics in both discrete and computational geometry, as well as in a number of applied areas. These include geometric data structures, polytopes and polyhedra, convex hull and triangulation algorithms, packing and covering, Voronoi diagrams, combinatorial geometric questions, computational convexity, shortest paths and networks, computational real algebraic geometry, geometric arrangements and their complexity, geometric reconstruction problems, randomization and de-randomization techniques, ray shooting, parallel computation in geometry, oriented matroids, computational topology, mathematical programming, motion planning, sphere packing, computer graphics, robotics, crystallography, and many others. A final chapter is devoted to a list of available software. Results are presented in the form of theorems, algorithms, and tables, with every technical term carefully defined in a glossary that precedes the section in which the term is first used. There are numerous examples and figures to illustrate the ideas discussed, as well as a large number of unsolved problems.

The main body of the volume is divided into six parts. The first two, on combinatorial and discrete geometry and on polytopes and polyhedra, deal with fundamental geometric objects such as planar arrangements, lattices, and convex polytopes. The next section, on algorithms and geometric complexity, discusses these basic geometric objects from a computational point of view. The fourth and fifth sections, on data structures and computational techniques, discuss various computational methods that cut across the spectrum of geometric objects, such as randomization and de-randomization, and parallel algorithms in geometry, as well as efficient data structures for searching and for point location. The sixth section, which is the longest in the volume, contains chapters on fourteen applications areas of both discrete and computational geometry, including low-dimensional linear programming, combinatorial optimization, motion planning, robotics, computer graphics, pattern recognition, graph drawing, splines, manufacturing, solid modeling, rigidity of frameworks, scene analysis, error-correcting codes, and crystallography. It concludes with a fifteenth chapter, an up-to-the-minute compilation of available software relating to the various areas covered in the volume. A comprehensive index follows, which includes proper names as well as all of the terms defined in the main body of the Handbook.

A word about references. Because it would have been prohibitive to provide complete references to all of the many thousands of results included in the Hand-book, we have to a large extent restricted ourselves to references for either the most important results, or for those too recent to have been included in earlier survey books or articles; for the rest we have provided annotated references to easily accessible surveys of the individual subjects covered in the Handbook, which themselves contain extensive bibliographies. In this way, the reader who wishes to pursue an older result to its source will be able to do so.

This second edition of the Handbook of Discrete and Computational Geometry rep-resents a substantial revision of the first edition, published seven years earlier. The new edition has added over 500 pages, a growth by more than 50%. Each chapter has been thoroughly revised and updated, and we have added thirteen new chapters. The additional room permitted the expansion of the curtailed bibliographies of the first edition, which often required citing other surveys to locate original sources. The new bibliographies make the chapters, insofar as is possible, self-contained. Most chapters have been revised by their original authors, but in a few cases new authors have joined the effort. All together, taking into account the chapters new to this edition, the number of authors has grown from sixty-three to eighty-two.

In the first edition there was one index; now there are two: in addition to the Index of Defined Terms there is also an Index of Cited Authors, which includes everyone referred to by name in either the text or the bibliography of each chap-ter. The first edition chapter on computational geometry software has been split into two chapters: one on the libraries LEDA and CGAL, the other on additional software. There are five new chapters in the applications section: on algorithms for modeling motion, on surface simplification and 3D-geometry compression, on statistical applications, on Geographic Information Systems and computational cartography, and on biological applications of computational topology. There are new chapters on collision detection and on nearest neighbors in high-dimensional spaces. We have added material on mesh generation, as well as a new chapter on curve and surface reconstruction, and new chapters on embeddings of finite metric spaces, on polygonal linkages, and on geometric graph theory.

All of these new chapters, together with the many new results contained within the Handbook as a whole, attest to the rapid growth in the field since preparation for the first edition began a decade ago. And as before, we have engaged the world's leading experts in each area as our authors.Geometric Sturmian Theory of Nonlinear Parabolic Equations with Applications by Victor A. Galaktionov (Chapman & Hall/CRC) Unlike the classical Sturm theorems on the zeros of solutions of second-order ODEs, Sturm's evolution zero set analysis for parabolic PDEs did not attract much attention in the 19th century, and, in fact, it was lost or forgotten for almost a century. Briefly revived by Pólya in the 1930s and rediscovered in part several times since, it was not until the 1980s that the Sturmian argument for PDEs began to penetrate into the theory of parabolic equations and was found to have several fundamental applications.

Geometric Sturmian Theory of Nonlinear Parabolic Equations and Applications focuses on geometric aspects of the intersection comparison for nonlinear models creating finite-time singularities. After introducing the original Sturm zero set results for linear parabolic equations and the basic concepts of geometric analysis, the author presents the main concepts and regularity results of the geometric intersection theory (G-theory). Here he considers the general singular equation and presents the geometric notions related to the regularity and interface propagation of solutions. In the general setting, the author describes the main aspects of the ODE-PDE duality, proves existence and nonexistence theorems, establishes uniqueness and optimal Bernstein-type estimates, and derives interface equations, including higher-order equations. The final two chapters explore some special aspects of discontinuous and continuous limit semigroups generated by singular parabolic equations.

Much of the information presented here has never before been published in book form or even in mathematics journals. Readable and self-contained, this book forms a unique and outstanding reference on second-order parabolic PDEs used as models for a wide range of physical problems.

This book is devoted to nonlinear second-order parabolic equations including well-known reaction-diffusion-absorption models from combustion, heat conduction and nonstationary filtration theory. Galaktionov considers typical questions such as existence, nonexistence, uniqueness and regularity properties of solutions to nonlinear equations admitting blow-up, extinction, or other types of evolution singularities with finite propagation and free boundaries. The ideas and techniques used in the analysis are purely geometric and their cornerstone is the Sturm theory of zeros of solutions of one-dimensional linear parabolic equations.

In 1836 C. Sturm published two celebrated papers in the first volume of J. Liouville's Journal de Mathématique Pures et Appliquées. The first paper on zeros of solutions of second-order ordinary differential equations very quickly exerted a great influence on the general theory of ODEs. Then and nowadays Sturm oscillation, comparison and separation theorems can be found in most textbooks on ODEs with various generalizations to other equations and systems of equations. Such theorems classify and compare zeros and zero sets of different solutions, or solutions of equations with different continuous ordered potentials.

The second paper was devoted to the evolution analysis of zeros and zero sets for solutions of partial differential equations of parabolic type, for instance, of the heat equation with a linear term as in with the Dirichlet boundary condition and given smooth initial data. Sturm results on PDEs can be stated as follows:

First Sturm Theorem: nonincrease with time of the number of zeros (or sign changes) of solutions, Second Sturm Theorem: a classification of blow-up self-focusing formations and collapses of multiple zeros.

Galaktionov refers to both Sturm Theorems together as the Sturmian argument on zero sets. Most of Sturm's PDE paper was devoted to the second Theorem on striking evolution "dissipativity" properties of zeros of solutions of linear parabolic equations, where a detailed backward-forward continuation analysis of the col-lapse of multiple zeros of solutions was performed. The first Theorem was formulated as a consequence of the second one (it is a form of the strong Maximum Principle for parabolic equations). As a by-product of the first Theorem, Sturm presented an evolution proof of bounds of the number of zeros of eigenfunction expansions. For finite Fourier series, by using the PDE (0.2), where q = 0 (with periodic boundary conditions), he showed that f (x) has at least 2L and at most 2M zeros. Sometimes the lower bound on zeros is referred to as the Hurwitz Theorem, which, possibly, was better known than the first Sturm PDE Theorem. This Sturm-Hurwitz Theorem is the origin of many striking results, ideas and conjectures in topology of curves and symplectic geometry.

Unlike the classical Sturm theorems on zeros of solutions of second-order ODEs, Sturm's evolution zero set analysis for parabolic PDEs did not attract much attention in the nineteenth century and, in fact, was forgotten for almost a century. It seems that G. Pólya (1933) [296] was the first mathematician in the twentieth century to revive interest in the first Sturm Theorem for the heat equation. The earlier extension by A. Hurwitz (1903) [200] of Sturm's result on zeros of (0.3) to infinite Fourier series with M = oo did not use parabolic PDEs. Since the 1930s the Sturmian argument has been rediscovered in part several times. For instance, a key idea of the Lyapunov monotonicity analysis in the famous KPP-problem by A.N. Kolmogorov, I.G. Petrovskii and N.S. Piskunov (1937) on the stability of traveling waves (TWs) in reaction-diffusion equations, was based on the first Sturm Theorem in a simple geometric configuration with a single intersection between solutions. This was separately proved there by the Maximum Principle.

From the 1980s the Sturmian argument began to penetrate more and more into the theory of linear and nonlinear parabolic equations and was found to have several fundamental applications. These include asymptotic stability theory for various nonlinear parabolic equations, orbital connections and transversality of stable-unstable manifolds for semilinear parabolic equations as Morse-Smale systems, unique continuation theory, Roquet bundles and a Poincaré-Bendixson Theorem for parabolic equations, problems of symplectic geometry and curve shortening flows. A survey on Sturm's ideas in parabolic PDEs is presented in Chapter 1, where Galaktionov includes the proofs of both Sturm Theorems and describe further related results and generalizations achieved in the twentieth century.

Among many reasons stimulating the fundamental importance of the Sturmian argument to be characterized later on, Galaktionov emphasizes the geometric and the asymptotic stability aspects related to the context of the book. In this period, a number of essentially nonlinear reaction-diffusion equations from different areas of applications in mechanics and physics attracted the attention of mathematicians. A key feature of many such models is their nonlinear character and highly nonstationarybehaviour of solutions, leading to the formation of fret boundaries and finite-time singularities like blow-up; extinction, quenching, self-focusing, etc. On the other hand, as models from mechanics and physics based on fundamental conservation laws, these equations often inherit scaling invariance and admit groups of transformation, and hence different particular exact invariant solutions describing singularity formation phenomena. Then it is necessary to prove that such exact solutions are stable near singularities and are attractors of a wide class of more arbitrary solutions. The stability concept is extremely fruitful in evolution PDEs, but very often rigorous proofs are extremely hard even for simple nonlinear models, especially if stability of a singular blow-up process is studied.

In view of their clear geometric nature, Sturm zero-set ideas became a powerful tool of the asymptotic analysis of parabolic PDEs. It turned out that the structure and time-evolution of intersections of pairs of different solutions (that are zeros of the differences satisfying linear parabolic equations) can reveal the actual asymptotic behaviour of general solutions. In other words, some important properties of general solutions can be described by using the intersection comparison with families of particular exact solutions. Ideas of comparison were always important in the theory of nonlinear parabolic equations. Particular solutions or super and subsolutions satisfying the corresponding partial differential inequalities are used in the barrier analysis, yielding a priori bounds on classes of solutions by the Maximum Principle. Effective barrier approaches form the basis of the classical theory of nonlinear parabolic equations. But in the case of singular finite-time blow-up behaviour, the usual comparison is not sufficient and, actually, is good for nothing: no pairs of solutions to be compared in the usual sense exist since these must always intersect each other at any moment in time. Instead, the ideas of the intersection comparison with the control of the number of intersections and also their characters then begin to play a key role. This part of the geometric analysis is covered by Sturm Theorems.

This book concentrates on geometric aspects of the intersection comparison for nonlinear models creating finite-time singularities. A general principle of the analysis is as follows: given a sufficiently wide (we call it complete, in a natural geometric sense) subset of particular solutions, we perform intersection comparison analysis based on the Sturmian argument involving an infinite number of such "characteristic" solutions. Galaktionov calls such analysis the geometric intersection theory or the G-theory, for short, of nonlinear singular parabolic equations. The goal is to show that, for a wide class of such equations, the existence, nonexistence and a substantial part of the regularity theory can be reconstructed by means of known proper functional subsets of characteristic solutions. This is done by using simple geometric principles of comparison, transversality and convexity. These principles of ordered geometric flows (explained in Chapter 1 after two Sturm's Theorems) are the only machinery of intersection comparison Galaktionov is going to use here. The author does not apply other techniques that can be efficient for more specific classes of equations.
A.D. Alexandrov Selected Works: Intrinsic Geometry of Convex Surfaces edited
by S. S. Kutateladze (Classics of Soviet Mathematics: Gordon & Breach Publishing
Group) The 2-volume set includes Alexandrov: Selected Works, Part 1, Hb ISBN
2881249841, 1996, 332 pp, and Alexandrov, Selected Works, Part 2, Hb 041529802
4, 2003, 504 pp. The 2-volume set provides definitive sources for the
development of intrinsic geometry. A classic in the field that remains
unsurpassed in its clarity and scope, this text would be of great value to
graduate students seeking a better understanding of this area of geometry.

A.D. Alexandrov: Selected Works by A. D. Aleksandrov (Classics of Soviet
Mathematics: Gordon & Breach Publishing Group) This monograph offers any student
or professional working in the field a unique access to a selection of
Aleksandrov's best quality work, published here for the first time in English
translation.

This volume contains some of the most important papers by this world class
mathematician, who exerted such a powerful influence on the development of
modern mathematics. Aleksandrov was particularly noted for his work in geometry,
and the 16 papers included in this volume represent some of his most seminal
work. Topics treated include convex polyhedrons and closed surfaces, an
elementary proof and extension of Minkowski's theorm, a chapter in Riemannian
geometry and general method for majorizing the solutions of Dirichlet problems.
At present there is no such collection of this extremely well respected
geometer's work.

A.D. Alexandrov: Selected Works Part II: Intrinsic Geometry of Convex Surfaces
by S. S. Kutateladze (Classics of Soviet Mathematics: Gordon & Breach Publishing
Group) A.D. Alexandrov's contribution to the field of intrinsic geometry was
original and very influential. This text is a classic that remains unsurpassed
in its clarity and scope. It presents his core material, originally published in
Russian in 1948, beginning wth an outline of the main concepts and then
exploring other topics, such as general propositions on an intrinsic metric;
angles and curvature; existence of a convex polyhedron with prescribed metric;
curves on convex surfaces; and the role of specific curvature. This text
provides Adefinitive source for the development of intrinsic geometry and is
indispensable for graduate students who want a better understanding of this
subject.

*
Geometry: Our Cultural Heritage* by Audun Holme (Springer Verlag) is
based on lectures on geometry at the University of Bergen, Norway. Over the
years these lectures have covered many different aspects and facets of this
wonderful field. Consequently it has of course never been possible to give a
full and final account of geometry as such, at an undergraduate level: A
carefully considered selection has always been necessary. The present book
constitutes the main central themes of these selections.

One of the groups I am aiming at, is future teachers of mathematics. All too often the geometry which goes into the syllabus for teacher‑students present the material as pedantic and formalistic, suppressing the very powerful and dynamic character of this old ‑ and yet so young! ‑ field. A field of mathematical insight, research, history and source of artistic inspiration. And not least important, a foundation for our common cultural heritage.

Another motivation is to provide an invitation to mathematics in general. It is an unfortunate fact that today, at a time when mathematics and knowledge of mathematics is more important than ever, phrases like math avoidance and math anxiety are very much in the public vocabulary. An important task is seriously attempting to heal these ills. Ills perhaps inflicted on students at an early age, through deficient or even harmful teaching practices. Thus the book also aims at an informed public, interested in making a new beginning in math. And in doing so, learning more about this part of our cultural heritage.

The book is divided into two parts. Part 1 is called A Cultural Heritage. The section contains material that is normally not included into a mathematical text. For example, we relate some of the stories told by the Greek historian, Herodotus. We also include some excursions into the history of geometry. These excursions do not represent an attempt at writing the history of geometry. To write an introduction to the history of geometry would be a quite different and very challenging undertaking. Even for the period up to the beginning of the Middle Ages it would vastly surpass what is presently undertaken in.

To write the History of Geometry is therefore definitely not my aim with Part I of the present book. Instead, I wish to seek out the roots of the themes to be treated in Part 2, Introduction to Geometry. These roots include not only the geometric ideas and their development, but also the historical context. Also relevant are the legends and tales ‑ really fairy‑tales ‑ told about, for example, Pythagoras. Even if some of the more or less fantastic events of Iamblichus' writings are unsubstantiated, these stories very much became our perception of the geometry of Pythagoras, and thus became part of the heritage of geometry, if not of its history.

In Chapters 1 and 2 we go back to the beginnings of science. As geometry represents one of the two oldest fields of mathematics, we find it in evidence from the early beginnings. The other field being Number Theory, they go back as far as written records exist. Moreover, in the first written accounts from ancient civilizations they present themselves as already well-developed and sophisticated disciplines.

Thus we find that problems which ancient mathematicians thought about several thousand years ago, in many cases are the same problems that are stumbling stones for the students of today. As we move on in Chapters 3 and 4, we find that great minds like Archimedes, Pythagoras, Euclid and many, many others should be allowed to speak to the people of today, young and old. They are unsurpassable tutors.

The mathematical insight that Archimedes regarded as his most profound theorem, was a theorem on geometry which was inscribed on Archimedes' tombstone. All of us, from college student to established mathematician, must feel humbled by it. What does it say? Simply that if a sphere is inscribed in a cylinder, then the proportion of the volume of the cylinder to that of the sphere, is equal to the proportion of the corresponding surface areas, counting of course top and bottom of the cylinder. The common proportion is 2. This is a truly remarkable achievement for someone who did not know about integration, not know about limits, not know about... Its beauty and simplicity beckons us. How did Archimedes arrive at this result? Archimedes deserves to be remembered for this, rather for the silly affair of him having run out into the street as God had created him, shouting ‑ Eureka, Eureka! But the story may well be true, his absentmindedness under pressure cost him dearly in the end.

Pythagoras and his followers certainly did not discover the so‑called Pythagorean Theorem. The Babylonians, and before them the Sumerians, not only knew this fact very well, they also had the sophisticated number theoretical tools for constructing all Pythagorean triples, that is to say, all natural numbers a, b and d such that a2 + b2 = d2. And the astronomers and engineers ‑ or, if we prefer, the astrologers and priests ‑ of ancient Babylonia, or Mesopotamia, used these insights to construct trigonometric tables. Tables which were simple, accurate and powerful thanks to the sexagesimal system they used for representing numbers. What a challenging project for interested college students to understand the math of the Plimpton 322 tablet at Columbia University! And to correct and explain the four mistakes in it. Or finally to construct the successor or the predecessor of this tablet in the series it must have belonged to.

So what did Pythagoras discover himself? We know nothing with certainty of Pythagoras' life before he appeared on the Greek scene in midlife. Some say that he traveled to Egypt, where he was taken prisoner by the legendary, in part infamous, Persian King Cambyses II, who also ruled Babylon, which had been captured by his father Cyrus IL Pythagoras was subsequently brought to Babylon as a prisoner, but soon befriended the priests, the Magi, and was initiated into the priesthood in the temple of Marduk. We tell this story as related by Herodotus and Iamblichus. However, the accounts given in these classical books are not always historically correct, the reader should consult the footnotes to get a flavor of the present state of Herodotus, The Father of History, by some of his critics labeled The Father of Lies! But Herodotus is a fascinating story‑teller, and the place occupied by Pythagoras today has considerably more to do with the legends told about him than with what actually happened. So with this warning, do enjoy the story.

Euclid's Elements represents a truly towering masterpiece in the development of mathematics. Its influence runs strong and clear throughout, leading to non‑Euclidian geometry, Hilbert's axioms and a deeper understanding of the foundations of mathematics. The era that Euclid was such an eminent representative of, ended with the murder of another geometer: Hypatia of Alexandria.

In Chapter 5 we describe how the foundation of present day geometry was created. Elementary Geometry is tied to straight lines and circles. The theorems are closely tied to constructions with straightedge and compass, reflecting the postulates of Euclid. In higher geometry one moves on to the more general class of conic sections, as well as curves of higher degrees.

Descartes introduced ‑ or reintroduced, depending on your point of view ‑ algebra into the geometry. At any rate, he is credited with the invention of the Cartesian coordinate system, which is named after him.

In Chapter 6, the last chapter of Part 1, we discuss the relations between geometry and the real world. The qualitative study of catastrophes is of a geometric nature. We explain the simplest one among Thom's Elementary Catastrophes, the so‑called Cusp catastrophe. It yields an amazing insight into occurrences of abrupt events in the real world.

Also tied to the real world are the fractal structures in nature. Fractals are geometric objects whose dimensions are not integers, but which instead have a real number as dimension. Strange as this sounds, it is a natural outgrowth of Felix Hausdorff's theory of dimensions. Hausdorff was one of the pioneers of the modern transformation of geometry, referred to in his time as the High Priest of point‑set topology. In the end, this all did not help him. He knew, being a Jew, what to expect when he was ordered to report the next morning for deportation. This was in 1942 in his hometown of Bonn. Germany. Instead of doing so, Hausdorff and his wife committed suicide.

The Geometry of fractals shows totally new and unexpected geometric phenomena. Amazingly, what was thought of as pathology, as useless curiosities, may turn out to give the most precise description of the world we live in.

In Part 2, Introduction to Geometry, we take as our starting point the axiomatic treatment of geometry flowing from Euclid.

Euclid's original system of axioms and postulates passed remarkably well the test of modern demands to rigor. But an explanation was nevertheless very much called for, as his original system was set on a somewhat shaky foundation by our current mathematical standards. This clarifying explanation of the foundations was provided by Hilbert. The search for a proof of Euclid's Fifth Postulate at an earlier age, had met with no success. One version of this postulate asserts that there is one and only one line parallel to a given line through a point outside it.

Assuming the converse, one wanted to derive a contradiction. But instead the relentless toil produced alternatives to Euclidian Geometry. This was a highly troubling development for an age in which non‑Euclidian Geometry would appear as heretic as "Darwinism" appears in some circles today. We explain non‑Euclidian Geometry in Chapter 9. But first we need to do some serious work on foundations. We start with Logic and Set Theory. In fact, the Intuitive Set Theory, even as put on a firmer foundation by Cantor, turned out to imply grave contradictions. The best known is the so‑called Russell's Paradox, which we explain in Section 7.3.

Thus arouse the need for Axiomatic set theory, to which we give an introduction. The aim is to give a flavor of the field without going into the technical details at all.

We then explain the interplay between axiomatic theories and their models in Sections 7.3 and 7.4. The troubling result of Godel is explained, in simplified terms, showing that a mathematical Tower of Babel as perhaps dreamt of by Hilbert, is not possible: Any axiomatic system without contradictions among its possible consequences, will have to live with some undecidable statements. That is to say, statements that are perfectly legal constructions within the system, being inherently undecidable: Their truth or falsehood cannot be ascertained from the system itself.

In Chapter 8 we apply these insights to axiomatic projective geometry. This is an extensive field in itself, and a complete treatment does of course, fall outside the scope of this book. But we give a basic set of axioms, to which other may be added, thus in the end culminating with a set which determines uniquely the real, projective plane. This is not on our agenda here. But we do give, in some detail, two important models for the basic system of axioms. The Seven Point Plane and the real projective plane p2(R). That the simple axioms still hold intriguing open problems, is explained in Section 8.2. Use of powerful computers in conjunction with dexterous programming holds great promise for new insights, thus there exist ample possibilities for exiting research.

In Chapter 9 we are ready to explain models for non‑Euclidian Geometry. In the hyperbolic plane there are infinitely many lines parallel to a given line through a point outside it. In the elliptic plane there are no parallel lines:

Two lines always intersect. A model for this version is provided by 11°2(118).

Plane non‑Euclidian geometries have, of course, their spatial versions. This is best understood by turning to some of the basic facts from Riemannian Geometry, which we do in Section 9.5.

Chapter 10 contains some much needed mathematical tools, simple but essential. We need them for constructions to be carried out in following chapters, where we employ these standard techniques. The reader is advised to take the moments needed to ingest this material, which may well appear somewhat dry and barren at the first encounter.

In Chapter 11 we are now able to give coordinates in the projective plane, introduce projective n‑space and discuss affine and projective coordinate systems. Again, the material may appear dry, but the reader will be rewarded in Chapter 12. There we use these techniques to give the remarkably simple proof of the theorem of Desargues. We introduce duality for P2(R) and start the theory of conic sections in R2 and l(n2 (R) discussing tangency, degeneracy and the familiar classification of the conic sections. Pole and Polar belong to this picture, as well as a very simple proof of a famous theorem of Pascal.

Using it, we then prove the theorem of Pappus by a classical technique known as degeneration, or as the principle of continuity. Here we give the first, naive, definition of an algebraic curve.

In Chapter 13 we find the transition to the study of curves of degrees greater than 2. This forms the fundament for Algebraic Geometry, and gives a glimpse into an important and very rich, active and expanding mathematical field. Here we encounter the cubical parabola, merely a fancy name for a familiar curve, but also the enigmatic semi cubical parabola, so important in modern Catastrophe Theory. However, as we shall see in the following chapter, in Chapter 14, from a projective point of view these two kinds of affine curves are the same! This is shown at the end of Section 14.5. We also learn about the Folium of Descartes, the Trisectrix of Maclaurin, of Elliptical Curves which are by no means ellipses! ‑ and much more. Chapter 14 concludes with Pascal's Mysterium Hexagrammicum, which may be obtained as a beautiful application of Pascal's Theorem: Dualizing it the Mystery of the Hexagram is revealed.

In Chapter 15, as the title says, we sharpen the Sword of Algebra. The aim is to show how one finally disposes of the three problems, which have haunted mathematicians and amateurs for two millenia. And unfortunately, still does haunt the latter. The algebra derives in large part from the heritage of Euclid, relying as it does on Euclid's algorithm. This mathematics also constitutes the foundation for the important field of Galois theory and the theory of equations and their solvability by radicals. That theme is, however, not treated in the present book.

In Chapter 16 we use this algebra for proving that the three classical problems are insoluble: Trisecting an angle with legal use of straightedge and compass, doubling the cube using straightedge and compass, and finally we see how the transcendency of the number 7r precludes the squaring of the circle using straightedge and compass. Gauss' towering achievement on constructibility of regular polygons conclude the chapter. The solution of this problem by Gauss transformed the final answer to the geometric problem into a number theoretic problem on the existence of certain primes, namely primes of the form F,. = 2 2' + 1, the so‑called Fermat primes . For r = 0,1, 2, 3, 4 the numbers Pr are 3, 5,17, 257 and 65537. They are all primes, but then no case of an r yielding a prime is known. Gauss proved that if q is a product of such primes P,., all of them distinct, then the regular n = 2'°q‑gon may be constructed with straightedge and compass, and that this is precisely all the constructible cases. Thus for example the regular 3‑gon, the regular 5‑gon and the regular 15‑gon are all constructible with straightedge and compass, as is the regular 30‑gon and the regular 60‑gon. The first impossible case is the regular 7‑con. Now Archimedes constructed the regular 7‑gon, but he used means beyond legal use of straightedge and compass. In Section 4.4 we have given Archimedes' construction of the regular 7‑gon, the regular heptagon, by a so‑called verging construction. It is not possible by the legal use of compass and straightedge, but may be carried out by conic sections or by a curve of degree 3. In fact, such constructions were very much part of the motivation for passing from elementary geometry to higher geometry in the first place.

In Chapter 17 we take a closer look at the theory of fractals. We explain the computation of fractal dimensions.

Chapter 18 contains a mathematical treatment of introductory Catastrophe Theory. We explain the Cusp Catastrophe as an application of geometry on a cubic surface. For this we also explain some rudiments of Control Theory.*
Euclidean and Non-Euclidean Geometries* by Maria Helena Noronha (Prentice
Hall) is to be used in undergraduate geometry courses at the junior‑senior
level. It develops a self‑contained treatment of classical

Euclidean geometry through both axiomatic and analytic methods. In addition, the text integrates the study of spherical and hyperbolic geometry. Euclidean and hyperbolic geometries are constructed upon a consistent set of axioms, as well as presenting the analytic aspects of their models and their isometries. It also contains a study of the Euclidean n‑space.

The text differs from the traditional textbooks on the foundations of geometry by taking a more natural route that leads to non-Euclidean geometries. The topics presented not only compare different parallel postulates, but place a certain emphasis on analytic aspects of some of the non‑Euclidean geometries. I intend to show students how theories that underlie other fields of mathematics can be used to better understand the concrete models for the axiom systems of Euclidean, spherical, and hyperbolic geometries and to better visualize the abstract theorems. I use elementary calculus to compute lengths of curves in 3‑space and on spheres, a topic usually found at the beginning of elementary books on differential geometry.

Another feature of this book is the inclusion in the text of a few topics in linear algebra and complex variable. I treat those topics (and only those) that will be used in the book. They are introduced as needed to advance in the study of geometry. I do not assume any prior knowledge of complex variable and only a few basic facts about matrices.

The topics of linear algebra are used to do a more advanced study of rigid motions of the n‑dimensional Euclidean space, while complex variables are used to thoroughly study two models of the hyperbolic plane. This text also describes the connections between the study of geometric transformations and transformations groups ‑-- for example, showing how a dihedral group is realized as the symmetry group of a regular polygon.

The prerequisites for reading this book should be quite minimal. It has been written not presupposing any knowledge of Euclidean and analytic geometry. However, basic elementary set theory is required for the axiomatic geometry part. The part containing the analytic methods is basically self‑contained, assuming only that the students have had a basic single‑variable calculus course.

The book has been written assuming that a standard mathematical curriculum contains at most two semesters of geometry. Although some beautiful topics, such as projective geometry, have been left out, I believe that I have chosen crucial aspects of classical and modern geometry that provide an accessible introduction to advanced geometry.

It is not unreasonable for the instructor to hope to cover the whole book in one year. Of course, it depends on the ability and experience of his/her students. But if some choices have to be made, the book is organized to permit a number of one‑ or two‑semester course outlines so that instructors may follow their preferences. Moreover, I have attempted to discuss all topics in detail, so that the ones not covered could be undertaken as independent study. Since Chapter 1 sets the tone for the whole book and Chapter 2 contains the classical results of plane Euclidean geometry, they form the core of the book.

It is possible to teach a course only on axiomatic geometry using this text. A one‑semester course on Euclidean and hyperbolic geometries using only axiomatic methods would be Chapters 1, 2, and 8. The instructor who wants to study hyperbolic geometry mainly through the Poincare models can move to Chapters 9 and 10 after having covered only Sections 8.1, 8.2 and 8.3. Likewise, in a one‑semester course, spherical geometry can be briefly studied in Section 9.1, which is independent of Chapter 7 where this topic is presented with some thoroughness. The diagram on page xv shows the dependencies among the various chapters, and the instructor can customize the coverage by choosing the desired topics.

This text fits very well the needs of an undergraduate in the secondary teaching option. It contains the classical Euclidean geometry required for obtaining a teaching credential, and it is an introduction to non‑Euclidean geometry. The majority of mathematics majors in the secondary teaching option are not required to take courses on advanced calculus and complex variables. It is for such majors that I wrote a self‑contained text. The book could also be used in an introductory graduate course for secondary or community college teachers. This text should also appeal to undergraduate mathematics majors interested in geometry. The analytic methods used in the text will complement and deepen the knowledge of certain areas of mathematics involved in such methods, including Euclidean geometry itself.

Throughout the text I follow the same guiding principles, precisely stating definitions and theorems. Proofs are presented in detail, and when some steps are missing the reader is told precisely from which exercises they will follow. A difficulty usually found at the beginning of courses that build a geometry upon a set of postulates is to have the students understand that results derived from these postulates hold in some of the non‑Euclidean geometries as well, and therefore their proofs cannot rely on facts obtained from their drawings. To clarify this point, in all proofs in the first sections of Chapter 1 I precisely indicate which axioms have been used. I also clearly point out assertions that follow from results that have already been proved. Likewise, after introducing the Euclidean parallel postulate in Chapter 2, I repeatedly point out in subsequent proofs where such a postulate or an equivalent result is used.

The degree of difficulty of exercises varies. Some have the purpose of only fixing the concepts or practicing a method, while others complete the results proved in the text or extend some of the theory, sometimes proving a result that will be needed later in the book. All challenging problems contain hints that should get the students started on the solution. Moreover, bearing in mind that to write logical and coherent proofs for theorems is a difficult task for beginners, in several exercises I sketch the proofs, and students are asked to justify the steps or explain the contradictions.

insert content here