Computing in Euclidean GeometryWorld Scientific, 1995 - 492 Seiten 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. |
Inhalt
Preface | 1 |
Probabilistic DivideandConquer | 2 |
Lower Bounds of | 10 |
Some Applications | 15 |
References | 20 |
A Retrospective | 22 |
Lower Bounds | 28 |
Combinatorial Geometry | 34 |
Definition of the Voronoi Diagram and Delaunay Triangulation | 228 |
Definitions from the Theory of Polyhedra | 260 |
Geometric Constraint Solving in R² and | 266 |
TwoDimensional Constraint Solving | 273 |
References | 298 |
Triangular Bézier Patches | 306 |
BPatches | 319 |
Bivariate BSplines | 327 |
Voronoi Diagrams and Delaunay Triangulations | 40 |
Mesh Generation and Optimal Triangulation | 47 |
Threedimensional Triangulations | 96 |
Conclusions | 110 |
Machine Proofs of Geometry Theorems | 124 |
Wus Method and Its Variants | 130 |
Algebraic vs Traditional Proofs | 141 |
Introduction | 146 |
Randomized Geometric Algorithms | 149 |
Appendix | 187 |
The State of Art on Steiner Ratio Problems | 195 |
Four Points | 201 |
Inner Spanning Trees | 209 |
References | 345 |
Computational Geometry and Topological Network Design | 351 |
Computational Geometry | 352 |
A Better Heuristic for a Arbitrary Metric Space | 372 |
Paradigms and Geometric Data Structures | 400 |
Geometric TND Problems | 409 |
Summary and Conclusions | 435 |
The Exact Computation Paradigm | 452 |
Applications of Exact Computation | 465 |
Theory of Exact Computation | 471 |
PrecisionDriven Computation | 479 |
Conclusions | 485 |
Andere Ausgaben - Alle anzeigen
Häufige Begriffe und Wortgruppen
ACM Symp algebraic algorithm angle applications approach B-patch B-splines Bézier Bézier patch boundary cells Chazelle circle circumsphere Clarkson clusters combinatorial Comp complexity computational geometry constraints construction contains convex hull convex polygons defined Delaunay triangulation Disc distance divide-and-conquer domain Edelsbrunner Euclidean example face facets Figure flip Geom geometric data structures geometry theorem given graph Gröbner basis Guibas halfspace heuristic IEEE Symp input points intersection Lemma line segments linear lower bound Matoušek mesh method minimum minimum spanning tree nodes O(n log O(n² octree optimal triangulation p₁ paradigm partition planar plane point set polyhedra polyhedron polynomial Proc proof PSLG quadtree query random subset range searching region regular points Seidel Sharir SIAM simple polygon simplex solution solved space spanning tree Steiner points Steiner ratio surface techniques tetrahedra theorem proving three-dimensional TND problems topology trapezoidal diagram triangular vector vertex vertices visible Voronoi diagrams Z-points