E-Book, Englisch, Band 151, 239 Seiten
Emiris / Sottile / Theobald Nonlinear Computational Geometry
1. Auflage 2009
ISBN: 978-1-4419-0999-2
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark
E-Book, Englisch, Band 151, 239 Seiten
Reihe: The IMA Volumes in Mathematics and its Applications
ISBN: 978-1-4419-0999-2
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark
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.
Autoren/Hrsg.
Weitere Infos & Material
1;FOREWORD;5
2;PREFACE;6
3;CONTENTS;9
4;SPECTRAL TECHNIQUES TO EXPLORE POINT CLOUDS IN EUCLIDEAN SPACE, WITH APPLICATIONS TO COLLECTIVE COORDINATES IN STRUCTURAL BIOLOGY;10
4.1;1. Introduction.;11
4.1.1;1.1. Geometric data analysis and spectral point cloud processing.;11
4.1.2;1.2. Spectral methods and alternatives.;12
4.1.3;1.3. An application in structural biology: Protein folding.;14
4.1.4;1.4. Notations and paper overview.;15
4.2;2. PCA and MDS.;15
4.2.1;2.1. PCA.;16
4.2.2;2.2. MDS.;17
4.3;3. Localization.;17
4.3.1;3.1. Neighborhood criteria.;17
4.3.2;3.2. Dimension detection using PCA.;18
4.4;4. Turning non-linear.;19
4.4.1;4.1. Maximum variance unfolding (MVU).;19
4.4.2;4.2. Locally linear embedding (LLE).;20
4.4.3;4.3. ISOMAP.;21
4.4.4;4.4. Laplacian eigenmaps.;21
4.4.5;4.5. Hessian eigenmaps (HLLE).;22
4.4.6;4.6. Diffusion maps.;23
4.5;5. Applications in structural biology: the folding problem.;24
4.5.1;5.1. Folding: from experiments to modeling.;25
4.5.2;5.2. Energy landscapes and dimensionality reduction.;25
4.5.2.1;5.2.1. Potential and free energy landscape.;25
4.5.2.2;5.2.2. Enthalpy-entropy compensation, energy funnel, ruggedness and frustration.;25
4.5.2.3;5.2.3. Cooperativity and correlated motions.;27
4.5.3;5.3. Bio-physics: Pre-requisites.;28
4.5.3.1;5.3.1. Molecular dynamics simulations.;28
4.5.3.2;5.3.2. Models, potential energy landscapes and their ruggedness.;28
4.5.3.3;5.3.3. Morse theory and singularity theory.;29
4.5.3.4;5.3.4. Free energy landscapes and reaction coordinates.;29
4.5.3.5;5.3.5. Folding probability pfold.;30
4.5.4;5.4. Inferring reaction coordinates.;33
4.5.4.1;5.4.1. Reaction coordinates?;33
4.5.4.2;5.4.2. Contacts based analysis.;33
4.5.4.3;5.4.3. Dimension reduction based analysis.;35
4.5.4.4;5.4.4. Morse theory related analysis.;36
4.6;6. Outlook.;37
4.7;Acknowledgments.;38
4.8;REFERENCES;38
5;RATIONAL PARAMETRIZATIONS, INTERSECTION THEORY, AND NEWTON POLYTOPES;44
5.1;1. Introduction.;44
5.2;2. The Newton polytope of the implicit equation.;46
5.2.1;2.1. The Newton polygon of a parametric curve.;49
5.2.2;2.2. Tropical geometry and Intersection Theory.;51
5.3;3. Some applications and consequences.;52
5.3.1;3.1. Computing the implicit equation with numerical interpolation.;52
5.3.2;3.2. Intersecting parametric curves.;53
5.4;4. The general case vs the generic case.;56
5.5;Acknowledgments.;58
5.6;REFERENCES;58
6;SOME DISCRETE PROPERTIES OF THE SPACE OFLINE TRANSVERSALS TO DISJOINT BALLS;60
6.1;1. Introduction.;60
6.1.1;1.1. Notations and terminology.;61
6.1.2;1.2. Content and organization.;62
6.1.3;1.3. Related surveys.;63
6.2;2. Helly's theorem.;63
6.2.1;2.1. Spherical Helly theorem.;63
6.2.2;2.2. Topological Helly theorem.;64
6.2.3;2.3. Helly's theorem for unions of sets.;64
6.2.4;2.4. Convexity structure on the Grassmannian.;65
6.3;3. Cone of directions.;65
6.3.1;3.1. Reduction.;65
6.3.2;3.2. Analytic approach.;66
6.3.3;3.3. Extending the analytic approach.;67
6.3.4;3.4. The algebraic approach.;68
6.3.5;3.5. Strict convexity and tangents to spheres.;69
6.3.6;3.6. Immediate consequences.;70
6.3.6.1;3.6.1. Topology of order-respecting transversals.;70
6.3.6.2;3.6.2. Isotopy and geometric permutations.;70
6.3.6.3;3.6.3. Pinning con gurations.;71
6.4;4. Geometric permutations.;71
6.4.1;4.1. Separation sets.;72
6.4.2;4.2. Switch pairs.;73
6.4.2.1;4.2.1. Properties of a switch pair.;74
6.4.2.2;4.2.2. Number of switch pairs.;74
6.4.2.3;4.2.3. Hamming distance between geometric permutations.;74
6.4.2.4;4.2.4. The case of unit balls.;74
6.4.3;4.3. Incompatible pairs.;75
6.4.3.1;4.3.1. Families with incompatible pairs.;75
6.4.3.2;4.3.2. The planar case.;76
6.4.3.3;4.3.3. Higher dimensions.;76
6.5;5. Pinning, Hadwiger and Helly numbers.;77
6.5.1;5.1. Relationship between the pinning and Hadwiger numbers.;77
6.5.2;5.2. Bounds on the pinning and Hadwiger numbers.;78
6.5.2.1;5.2.1. A simple quadratic bound.;78
6.5.3;5.3. A linear bound.;79
6.5.4;5.4. Helly numbers.;80
6.5.4.1;5.4.1. Designing an ordering.;80
6.5.4.2;5.4.2. The homotopy method.;81
6.5.4.3;5.4.3. Using Helly's theorem for unions of sets.;82
6.5.5;5.5. Lower bounds.;83
6.6;6. Algorithmic aspects.;84
6.6.1;6.1. Generalized linear programming.;85
6.6.2;6.2. LP-type formulation.;86
6.7;7. Some open problems.;88
6.8;Acknowledgements.;89
6.9;REFERENCES;89
7;ALGEBRAIC GEOMETRY AND KINEMATICS;93
7.1;1. Introduction.;93
7.2;2. Kinematic mapping.;93
7.2.1;2.1. Study’s kinematic mapping.;94
7.2.2;2.2. Fixed and moving frame.;96
7.2.3;2.3. Planar and spherical kinematic mapping.;98
7.2.4;2.4. Euclidean displacements and dual quaternions.;99
7.2.5;2.5. Geometry of the Study quadric.;101
7.3;3. Mechanism theory.;101
7.3.1;3.1. Serial and parallel manipulators.;104
7.4;4. Constraint varieties.;104
7.4.1;4.1. Kinematic image of elementary joints.;104
7.4.1.1;4.1.1. Revolute joints.;104
7.4.1.2;4.1.2. Prismatic joints.;105
7.4.1.3;4.1.3. Concatenation of joints.;105
7.4.1.4;4.1.4. Path constraints.;106
7.4.2;4.2. Mechanism analysis.;106
7.4.2.1;4.2.1. Direct and inverse kinematics.;107
7.4.2.2;4.2.2. Algebraic definition of degrees of freedom.;108
7.4.2.3;4.2.3. Workspace topology.;109
7.4.2.4;4.2.4. Mechanism singularities.;110
7.4.3;4.3. Mechanism synthesis.;113
7.5;REFERENCES;114
8;RATIONAL OFFSET SURFACESAND THEIR MODELING APPLICATIONS;116
8.1;1. Introduction and the history of rational offset surfaces.;116
8.2;2. Different approaches to rational offset surfaces.;118
8.2.1;2.1. Offsets as envelopes of spheres and planes.;118
8.2.2;2.2. The space of oriented planes and the Blaschke model.;119
8.2.3;2.3. The Blaschke image of a PN surface.;120
8.2.4;2.4. The Gaussian image of a PN surface.;121
8.2.5;2.5. Rational parametrizations of the unit sphere via stereo-graphic projection.;121
8.2.6;2.6. Rational parametrizations of PN surfaces in the simpleform.;121
8.3;3. Rational Surfaces with a linear normal vector field.;122
8.3.1;3.1. The Blaschke image of LN surfaces.;123
8.4;4. Laguerre geometry approach.;124
8.4.1;4.1. Gaussian sphere in projective Minkowski space.;124
8.4.2;4.2. Dual projective Minkowski space and the Blaschke cylinder.;126
8.4.3;4.3. Three models of Laguerre geometry.;126
8.4.4;4.4. Cyclographic images of parametric curves and surfaces in M.;127
8.5;5. Universal rational parametrizations of the sphere and theBlaschke cylinder.;128
8.6;6. Special cases of PN surfaces.;129
8.6.1;6.1. Canal surfaces.;129
8.6.2;6.2. Rational ruled surfaces in M.;131
8.6.3;6.3. Characterization of PN surfaces of low parametriza-tion degree.;132
8.6.4;6.4. Offsets of regular quadric surfaces in R3.;133
8.7;7. Modeling applications.;135
8.7.1;7.1. Modeling with parabolic cyclides.;136
8.7.2;7.2. Approximations with developable PN surfaces.;136
8.7.3;7.3. Blending natural quadrics with canal surfaces.;136
8.7.4;7.4. Branching blend of natural quadrics using non-canal PN surfaces.;138
8.8;8. Conclusions and open problems.;139
8.9;REFERENCES;140
9;A LIST OF CHALLENGES FOR REAL ALGEBRAIC PLANECURVE VISUALIZATION SOFTWARE;143
9.1;Introduction.;143
9.2;1. On correct visualizations of real algebraic plane curves.;144
9.2.1;1.1. An algorithm which produces correct visualizations.;145
9.2.2;1.2. The main visualization strategies.;145
9.3;2. Some notions from singularity theory.;146
9.4;3. Solitary points.;148
9.4.1;3.1. Many solitary points.;148
9.4.2;3.2. Higher solitary points.;149
9.5;4. Smooth curves with many components.;152
9.5.1;4.1. Harnack curves.;152
9.5.2;4.2. Nested ovals.;153
9.5.3;4.3. Small non–real ovals.;154
9.6;5. High tangencies at isolated singularities.;155
9.7;6. High tangencies at non–isolated singularities.;157
9.8;7. Many isolated singularities.;159
9.9;8. Complicated isolated singularities.;162
9.9.1;8.1. Ordinary singularities.;162
9.9.2;8.2. Some isolated singularitiesWith many halfbranches.;164
9.10;9. Other interesting examples.;166
9.10.1;9.1. Discriminants.;166
9.10.2;9.2. Plane curves with several difficulties.;167
9.11;REFERENCES;170
10;A SUBDIVISION METHOD FOR ARRANGEMENTCOMPUTATION OF SEMI-ALGEBRAIC CURVES;171
10.1;1. Geometric processing on semi-algebraic sets.;171
10.2;2. Subdivision approach and criterion of regularity.;173
10.2.1;2.1. Subdivision.;173
10.2.2;2.2. Regularity criterion.;174
10.2.3;2.3. Subdividing a cell.;175
10.2.4;2.4. Topology.;176
10.2.5;2.5. Fusion.;177
10.3;3. Region representation and computation.;178
10.3.1;3.1. Region representation.;178
10.3.2;3.2. Region segmentation.;179
10.3.3;3.3. Updating regions.;180
10.4;4. Algebraic operation on semi-algebraic sets.;182
10.4.1;4.1. Isolating real roots.;183
10.4.2;4.2. Implicit curves.;186
10.4.3;4.3. Parametric curves.;187
10.4.4;4.4. Piecewise linear curves.;188
10.5;5. Examples.;189
10.5.1;5.1. Concentric circles.;189
10.5.2;5.2. Singular implicit curves in degenerate configuration.;190
10.6;Summary and outlook.;191
10.7;REFERENCES;192
11;INVARIANT-BASED CHARACTERIZATION OF THERELATIVE POSITION OF TWO PROJECTIVE CONICS;194
11.1;1. Introduction.;194
11.2;2. Preliminaries.;196
11.3;3. Classi cation of intersections of conics.;197
11.4;4. Algebraic invariant theory: an overview.;199
11.4.1;4.1. Invariants of n-ary forms.;200
11.4.2;4.2. Key results.;202
11.4.3;4.3. Computing concomitants.;203
11.4.3.1;4.3.1. Transvection and Cayley's -process.;203
11.4.3.2;4.3.2. Polarization.;205
11.4.4;4.4. Pencils of conics.;206
11.5;5. Invariant theory of pairs of ternary quadratic forms.;207
11.5.1;5.1. Invariants.;207
11.5.2;5.2. Non-constant concomitants.;207
11.5.2.1;5.2.1. Preliminary result.;207
11.5.2.2;5.2.2. Covariants.;208
11.5.2.3;5.2.3. Contravariants.;209
11.5.3;5.3. Linking covariants and contravariants.;210
11.6;6. Combinants of pairs of ternary quadratic forms.;210
11.6.1;6.1. Invariant combinants.;210
11.6.2;6.2. Covariant combinants.;211
11.6.3;6.3. Geometric meaning.;213
11.7;7. Distinguishing between pencil orbits.;214
11.8;8. Isotopy classes and inside-outside test.;215
11.9;9. Examples.;218
11.9.1;9.1. Example 1.;219
11.9.2;9.2. Example 2.;219
11.10;10. Conclusion.;221
11.11;Acknowledgement.;221
11.12;APPENDIX;222
11.13;REFERENCES;223
12;A NOTE ON PLANAR HEXAGONAL MESHES;226
12.1;1. Introduction.;226
12.2;2. Existing methods.;230
12.3;3. A new method.;233
12.4;4. Offset mesh.;233
12.5;5. Further problems.;237
12.6;6. Acknowledgments.;238
12.7;REFERENCES;238
13;LIST OF WORKSHOP PARTICIPANTS;239
14;The IMA Volumes in Mathematics and its Applications;2
