Nonlinear Computational Geometry (eBook)

Ioannis Z. Emiris, Frank Sottile, Thorsten Theobald (Herausgeber)

eBook Download: PDF

2009 | 2010
XI, 239 Seiten
Springer New York (Verlag)
978-1-4419-0999-2 (ISBN)

Infos

An original motivation for algebraic geometry was to understand curves and surfaces in three dimensions. Recent theoretical and technological advances in areas such as robotics, computer vision, computer-aided geometric design and molecular biology, together with the increased availability of computational resources, have brought these original questions once more into the forefront of research. One particular challenge is to combine applicable methods from algebraic geometry with proven techniques from piecewise-linear computational geometry (such as Voronoi diagrams and hyperplane arrangements) to develop tools for treating curved objects. These research efforts may be summarized under the term nonlinear computational geometry.

This volume grew out of an IMA workshop on Nonlinear Computational Geometry in May/June 2007 (organized by I.Z. Emiris, R. Goldman, F. Sottile, T. Theobald) which gathered leading experts in this emerging field. The research and expository articles in the volume are intended to provide an overview of nonlinear computational geometry. Since the topic involves computational geometry, algebraic geometry, and geometric modeling, the volume has contributions from all of these areas. By addressing a broad range of issues from purely theoretical and algorithmic problems, to implementation and practical applications this volume conveys the spirit of the IMA workshop.

Inhalt

FOREWORD 5
PREFACE 6
CONTENTS 9
SPECTRAL TECHNIQUES TO EXPLORE POINT CLOUDS IN EUCLIDEAN SPACE, WITH APPLICATIONS TO COLLECTIVE COORDINATES IN STRUCTURAL BIOLOGY 10
1. Introduction. 11
1.1. Geometric data analysis and spectral point cloud processing. 11
1.2. Spectral methods and alternatives. 12
1.3. An application in structural biology: Protein folding. 14
1.4. Notations and paper overview. 15
2. PCA and MDS. 15
2.1. PCA. 16
2.2. MDS. 17
3. Localization. 17
3.1. Neighborhood criteria. 17
3.2. Dimension detection using PCA. 18
4. Turning non-linear. 19
4.1. Maximum variance unfolding (MVU). 19
4.2. Locally linear embedding (LLE). 20
4.3. ISOMAP. 21
4.4. Laplacian eigenmaps. 21
4.5. Hessian eigenmaps (HLLE). 22
4.6. Diffusion maps. 23
5. Applications in structural biology: the folding problem. 24
5.1. Folding: from experiments to modeling. 25
5.2. Energy landscapes and dimensionality reduction. 25
5.2.1. Potential and free energy landscape. 25
5.2.2. Enthalpy-entropy compensation, energy funnel, ruggedness and frustration. 25
5.2.3. Cooperativity and correlated motions. 27
5.3. Bio-physics: Pre-requisites. 28
5.3.1. Molecular dynamics simulations. 28
5.3.2. Models, potential energy landscapes and their ruggedness. 28
5.3.3. Morse theory and singularity theory. 29
5.3.4. Free energy landscapes and reaction coordinates. 29
5.3.5. Folding probability pfold. 30
5.4. Inferring reaction coordinates. 33
5.4.1. Reaction coordinates? 33
5.4.2. Contacts based analysis. 33
5.4.3. Dimension reduction based analysis. 35
5.4.4. Morse theory related analysis. 36
6. Outlook. 37
Acknowledgments. 38
REFERENCES 38
RATIONAL PARAMETRIZATIONS, INTERSECTION THEORY, AND NEWTON POLYTOPES 44
1. Introduction. 44
2. The Newton polytope of the implicit equation. 46
2.1. The Newton polygon of a parametric curve. 49
2.2. Tropical geometry and Intersection Theory. 51
3. Some applications and consequences. 52
3.1. Computing the implicit equation with numerical interpolation. 52
3.2. Intersecting parametric curves. 53
4. The general case vs the generic case. 56
Acknowledgments. 58
REFERENCES 58
SOME DISCRETE PROPERTIES OF THE SPACE OFLINE TRANSVERSALS TO DISJOINT BALLS 60
1. Introduction. 60
1.1. Notations and terminology. 61
1.2. Content and organization. 62
1.3. Related surveys. 63
2. Helly's theorem. 63
2.1. Spherical Helly theorem. 63
2.2. Topological Helly theorem. 64
2.3. Helly's theorem for unions of sets. 64
2.4. Convexity structure on the Grassmannian. 65
3. Cone of directions. 65
3.1. Reduction. 65
3.2. Analytic approach. 66
3.3. Extending the analytic approach. 67
3.4. The algebraic approach. 68
3.5. Strict convexity and tangents to spheres. 69
3.6. Immediate consequences. 70
3.6.1. Topology of order-respecting transversals. 70
3.6.2. Isotopy and geometric permutations. 70
3.6.3. Pinning con gurations. 71
4. Geometric permutations. 71
4.1. Separation sets. 72
4.2. Switch pairs. 73
4.2.1. Properties of a switch pair. 74
4.2.2. Number of switch pairs. 74
4.2.3. Hamming distance between geometric permutations. 74
4.2.4. The case of unit balls. 74
4.3. Incompatible pairs. 75
4.3.1. Families with incompatible pairs. 75
4.3.2. The planar case. 76
4.3.3. Higher dimensions. 76
5. Pinning, Hadwiger and Helly numbers. 77
5.1. Relationship between the pinning and Hadwiger numbers. 77
5.2. Bounds on the pinning and Hadwiger numbers. 78
5.2.1. A simple quadratic bound. 78
5.3. A linear bound. 79
5.4. Helly numbers. 80
5.4.1. Designing an ordering. 80
5.4.2. The homotopy method. 81
5.4.3. Using Helly's theorem for unions of sets. 82
5.5. Lower bounds. 83
6. Algorithmic aspects. 84
6.1. Generalized linear programming. 85
6.2. LP-type formulation. 86
7. Some open problems. 88
Acknowledgements. 89
REFERENCES 89
ALGEBRAIC GEOMETRY AND KINEMATICS 93
1. Introduction. 93
2. Kinematic mapping. 93
2.1. Study’s kinematic mapping. 94
2.2. Fixed and moving frame. 96
2.3. Planar and spherical kinematic mapping. 98
2.4. Euclidean displacements and dual quaternions. 99
2.5. Geometry of the Study quadric. 101
3. Mechanism theory. 101
3.1. Serial and parallel manipulators. 104
4. Constraint varieties. 104
4.1. Kinematic image of elementary joints. 104
4.1.1. Revolute joints. 104
4.1.2. Prismatic joints. 105
4.1.3. Concatenation of joints. 105
4.1.4. Path constraints. 106
4.2. Mechanism analysis. 106
4.2.1. Direct and inverse kinematics. 107
4.2.2. Algebraic definition of degrees of freedom. 108
4.2.3. Workspace topology. 109
4.2.4. Mechanism singularities. 110
4.3. Mechanism synthesis. 113
REFERENCES 114
RATIONAL OFFSET SURFACESAND THEIR MODELING APPLICATIONS 116
1. Introduction and the history of rational offset surfaces. 116
2. Different approaches to rational offset surfaces. 118
2.1. Offsets as envelopes of spheres and planes. 118
2.2. The space of oriented planes and the Blaschke model. 119
2.3. The Blaschke image of a PN surface. 120
2.4. The Gaussian image of a PN surface. 121
2.5. Rational parametrizations of the unit sphere via stereo-graphic projection. 121
2.6. Rational parametrizations of PN surfaces in the simpleform. 121
3. Rational Surfaces with a linear normal vector field. 122
3.1. The Blaschke image of LN surfaces. 123
4. Laguerre geometry approach. 124
4.1. Gaussian sphere in projective Minkowski space. 124
4.2. Dual projective Minkowski space and the Blaschke cylinder. 126
4.3. Three models of Laguerre geometry. 126
4.4. Cyclographic images of parametric curves and surfaces in M. 127
5. Universal rational parametrizations of the sphere and theBlaschke cylinder. 128
6. Special cases of PN surfaces. 129
6.1. Canal surfaces. 129
6.2. Rational ruled surfaces in M. 131
6.3. Characterization of PN surfaces of low parametriza-tion degree. 132
6.4. Offsets of regular quadric surfaces in R3. 133
7. Modeling applications. 135
7.1. Modeling with parabolic cyclides. 136
7.2. Approximations with developable PN surfaces. 136
7.3. Blending natural quadrics with canal surfaces. 136
7.4. Branching blend of natural quadrics using non-canal PN surfaces. 138
8. Conclusions and open problems. 139
REFERENCES 140
A LIST OF CHALLENGES FOR REAL ALGEBRAIC PLANECURVE VISUALIZATION SOFTWARE 143
Introduction. 143
1. On correct visualizations of real algebraic plane curves. 144
1.1. An algorithm which produces correct visualizations. 145
1.2. The main visualization strategies. 145
2. Some notions from singularity theory. 146
3. Solitary points. 148
3.1. Many solitary points. 148
3.2. Higher solitary points. 149
4. Smooth curves with many components. 152
4.1. Harnack curves. 152
4.2. Nested ovals. 153
4.3. Small non–real ovals. 154
5. High tangencies at isolated singularities. 155
6. High tangencies at non–isolated singularities. 157
7. Many isolated singularities. 159
8. Complicated isolated singularities. 162
8.1. Ordinary singularities. 162
8.2. Some isolated singularitiesWith many halfbranches. 164
9. Other interesting examples. 166
9.1. Discriminants. 166
9.2. Plane curves with several difficulties. 167
REFERENCES 170
A SUBDIVISION METHOD FOR ARRANGEMENTCOMPUTATION OF SEMI-ALGEBRAIC CURVES 171
1. Geometric processing on semi-algebraic sets. 171
2. Subdivision approach and criterion of regularity. 173
2.1. Subdivision. 173
2.2. Regularity criterion. 174
2.3. Subdividing a cell. 175
2.4. Topology. 176
2.5. Fusion. 177
3. Region representation and computation. 178
3.1. Region representation. 178
3.2. Region segmentation. 179
3.3. Updating regions. 180
4. Algebraic operation on semi-algebraic sets. 182
4.1. Isolating real roots. 183
4.2. Implicit curves. 186
4.3. Parametric curves. 187
4.4. Piecewise linear curves. 188
5. Examples. 189
5.1. Concentric circles. 189
5.2. Singular implicit curves in degenerate configuration. 190
Summary and outlook. 191
REFERENCES 192
INVARIANT-BASED CHARACTERIZATION OF THERELATIVE POSITION OF TWO PROJECTIVE CONICS 194
1. Introduction. 194
2. Preliminaries. 196
3. Classi cation of intersections of conics. 197
4. Algebraic invariant theory: an overview. 199
4.1. Invariants of n-ary forms. 200
4.2. Key results. 202
4.3. Computing concomitants. 203
4.3.1. Transvection and Cayley's -process. 203
4.3.2. Polarization. 205
4.4. Pencils of conics. 206
5. Invariant theory of pairs of ternary quadratic forms. 207
5.1. Invariants. 207
5.2. Non-constant concomitants. 207
5.2.1. Preliminary result. 207
5.2.2. Covariants. 208
5.2.3. Contravariants. 209
5.3. Linking covariants and contravariants. 210
6. Combinants of pairs of ternary quadratic forms. 210
6.1. Invariant combinants. 210
6.2. Covariant combinants. 211
6.3. Geometric meaning. 213
7. Distinguishing between pencil orbits. 214
8. Isotopy classes and inside-outside test. 215
9. Examples. 218
9.1. Example 1. 219
9.2. Example 2. 219
10. Conclusion. 221
Acknowledgement. 221
APPENDIX 222
REFERENCES 223
A NOTE ON PLANAR HEXAGONAL MESHES 226
1. Introduction. 226
2. Existing methods. 230
3. A new method. 233
4. Offset mesh. 233
5. Further problems. 237
6. Acknowledgments. 238
REFERENCES 238
LIST OF WORKSHOP PARTICIPANTS 239
The IMA Volumes in Mathematics and its Applications 2

Produkt-Details

• Erscheint lt. Verlag: 28.10.2009
• Reihe/Serie: The IMA Volumes in Mathematics and its Applications
• Reihe/Serie: The IMA Volumes in Mathematics and its Applications
• Zusatzinfo: XI, 239 p.
• Verlagsort: New York
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Algebra
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Geometrie / Topologie
• Themenwelt: Mathematik / Informatik ► Mathematik ► Statistik
• Themenwelt: Technik
• Schlagworte: Algebra • Algebraic Curve • Algebraic Geometry • Computational • Computational Geometry • Dimension • Geometry • Nonlinear
• ISBN-10: 1-4419-0999-0 / 1441909990
• ISBN-13: 978-1-4419-0999-2 / 9781441909992