This book is a collection of surveys and exploratory articles about recent developments in the field of computational Euclidean geometry. Topics covered include the history of Euclidean geometry, Voronoi diagrams, randomized geometric algorithms, computational algebra, triangulations, machine proofs, topological designs, finite-element mesh, computer-aided geometric designs and Steiner trees. This second edition contains three new surveys covering geometric constraint solving, computational geometry and the exact computation paradigm.
Computing is quickly making much of geometry intriguing not only for philosophers and mathematicians, but also for scientists and engineers. What is the core set of topics that a practitioner needs to study before embarking on the design and implementation of a geometric system in a specialized discipline? This book attempts to find the answer. Every programmer tackling a geometric computing problem encounters design decisions that need to be solved. This book reviews the geometric theory then applies it in an attempt to find that elusive "right" design.
From the reviews: "This book offers a coherent treatment, at the graduate textbook level, of the field that has come to be known in the last decade or so as computational geometry. ... ... The book is well organized and lucidly written; a timely contribution by two founders of the field. It clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics. It also points the way to the solution of the more challenging problems in dimensions higher than two." #Mathematical Reviews#1 "... This remarkable book is a comprehensive and systematic study on research results obtained especially in the last ten years. The very clear presentation concentrates on basic ideas, fundamental combinatorial structures, and crucial algorithmic techniques. The plenty of results is clever organized following these guidelines and within the framework of some detailed case studies. A large number of figures and examples also aid the understanding of the material. Therefore, it can be highly recommended as an early graduate text but it should prove also to be essential to researchers and professionals in applied fields of computer-aided design, computer graphics, and robotics." #Biometrical Journal#2
The central object of this book is the measure of geometric quantities describing N a subset of the Euclidean space (E ,), endowed with its standard scalar product. Let us state precisely what we mean by a geometric quantity. Consider a subset N S of points of the N-dimensional Euclidean space E , endowed with its standard N scalar product. LetG be the group of rigid motions of E . We say that a 0 quantity Q(S) associated toS is geometric with respect toG if the corresponding 0 quantity Q[g(S)] associated to g(S) equals Q(S), for all g?G . For instance, the 0 diameter ofS and the area of the convex hull ofS are quantities geometric with respect toG . But the distance from the origin O to the closest point ofS is not, 0 since it is not invariant under translations ofS. It is important to point out that the property of being geometric depends on the chosen group. For instance, ifG is the 1 N group of projective transformations of E , then the property ofS being a circle is geometric forG but not forG , while the property of being a conic or a straight 0 1 line is geometric for bothG andG . This point of view may be generalized to any 0 1 subsetS of any vector space E endowed with a groupG acting on it.
Until recently, almost all of the interactions between objects in virtual 3D worlds have been based on calculations performed using linear algebra. Linear algebra relies heavily on coordinates, however, which can make many geometric programming tasks very specific and complex-often a lot of effort is required to bring about even modest performance enhancements. Although linear algebra is an efficient way to specify low-level computations, it is not a suitable high-level language for geometric programming. Geometric Algebra for Computer Science presents a compelling alternative to the limitations of linear algebra. Geometric algebra, or GA, is a compact, time-effective, and performance-enhancing way to represent the geometry of 3D objects in computer programs. In this book you will find an introduction to GA that will give you a strong grasp of its relationship to linear algebra and its significance for your work. You will learn how to use GA to represent objects and perform geometric operations on them. And you will begin mastering proven techniques for making GA an integral part of your applications in a way that simplifies your code without slowing it down. * The first book on Geometric Algebra for programmers in computer graphics and entertainment computing * Written by leaders in the field providing essential information on this new technique for 3D graphics * This full colour book includes a website with GAViewer, a program to experiment with GA
This introduction to computational geometry focuses on algorithms. Motivation is provided from the application areas as all techniques are related to particular applications in robotics, graphics, CAD/CAM, and geographic information systems. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement.
The application of geometric algebra to the engineering sciences is a young, active subject of research. The promise of this field is that the mathematical structure of geometric algebra together with its descriptive power will result in intuitive and more robust algorithms. This book examines all aspects essential for a successful application of geometric algebra: the theoretical foundations, the representation of geometric constraints, and the numerical estimation from uncertain data. Formally, the book consists of two parts: theoretical foundations and applications. The first part includes chapters on random variables in geometric algebra, linear estimation methods that incorporate the uncertainty of algebraic elements, and the representation of geometry in Euclidean, projective, conformal and conic space. The second part is dedicated to applications of geometric algebra, which include uncertain geometry and transformations, a generalized camera model, and pose estimation. Graduate students, scientists, researchers and practitioners will benefit from this book. The examples given in the text are mostly recent research results, so practitioners can see how to apply geometric algebra to real tasks, while researchers note starting points for future investigations. Students will profit from the detailed introduction to geometric algebra, while the text is supported by the author's visualization software, CLUCalc, freely available online, and a website that includes downloadable exercises, slides and tutorials.
This monograph-like anthology introduces the concepts and framework of Clifford algebra. It provides a rich source of examples of how to work with this formalism. Clifford or geometric algebra shows strong unifying aspects and turned out in the 1960s to be a most adequate formalism for describing different geometry-related algebraic systems as specializations of one "mother algebra" in various subfields of physics and engineering. Recent work shows that Clifford algebra provides a universal and powerful algebraic framework for an elegant and coherent representation of various problems occurring in computer science, signal processing, neural computing, image processing, pattern recognition, computer vision, and robotics.
This textbook offers an introduction to differential geometry designed for readers interested in modern geometry processing. Working from basic undergraduate prerequisites, the authors develop manifold theory and Lie groups from scratch; fundamental topics in Riemannian geometry follow, culminating in the theory that underpins manifold optimization techniques. Students and professionals working in computer vision, robotics, and machine learning will appreciate this pathway into the mathematical concepts behind many modern applications. Starting with the matrix exponential, the text begins with an introduction to Lie groups and group actions. Manifolds, tangent spaces, and cotangent spaces follow; a chapter on the construction of manifolds from gluing data is particularly relevant to the reconstruction of surfaces from 3D meshes. Vector fields and basic point-set topology bridge into the second part of the book, which focuses on Riemannian geometry. Chapters on Riemannian manifolds encompass Riemannian metrics, geodesics, and curvature. Topics that follow include submersions, curvature on Lie groups, and the Log-Euclidean framework. The final chapter highlights naturally reductive homogeneous manifolds and symmetric spaces, revealing the machinery needed to generalize important optimization techniques to Riemannian manifolds. Exercises are included throughout, along with optional sections that delve into more theoretical topics. Differential Geometry and Lie Groups: A Computational Perspective offers a uniquely accessible perspective on differential geometry for those interested in the theory behind modern computing applications. Equally suited to classroom use or independent study, the text will appeal to students and professionals alike; only a background in calculus and linear algebra is assumed. Readers looking to continue on to more advanced topics will appreciate the authors’ companion volume Differential Geometry and Lie Groups: A Second Course.
The papers in this volume were selected for presentation at the Fourth Annual International Computing and Combinatorics Conference (COCOON’98), held on August 12–14, 1998, in Taipei. The topics cover most aspects of theoretical computer science and combinatorics related to computing. Submissions to the conference this year was only conducted electronically. Thanks to the excellent software developed by the system team of the Institute of Information Science, we were able to make virtually all communications through the World Wide Web. A total of 69 papers was submitted in time to be considered, of which 36 papers were accepted for presentation at the conference. In addition to these contributed papers, the conference also included four invited presentations by Christo Papadimitriou, Michael Fishcher, Fan Chung Graham and Rao Kosaraju. It is expected that most of the accepted papers will appear in a more complete form in scienti?c journals. Moreover, selected papers will appear in a special issue of Theoretical Computer Science. We thank all program committee members, their support sta? and referees for excellent work within demanding time constraints. We thank all authors who submitted papers for consideration. We are especially grateful to our colleagues who worked hard and o?ered widely di?ering talents to make the conference both possible and enjoyable. August 1998 Wen-Lian Hsu and Ming-Yang Kao Program Co-chairs COCOON’98 Organization COCOON’98 is organized by the Institute of Information Science, Academia Sinica, Taipei, Taiwan, ROC and in cooperation with Institute of Information and Computing Machinery (IICM), Taiwan, ROC.
