Computing in Euclidean GeometryThis book is a collection of surveys and exploratory articles about recent developments in the field of computational Euclidean geometry. The topics covered are: a 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. Each chapter is written by a leading expert in the field and together they provide a clear and authoritative picture of what computational Euclidean geometry is and the direction in which research is going. |
Contents
Preface | 1 |
Some Applications | 15 |
Mesh Generation and Optimal Triangulation | 23 |
Conclusions | 27 |
Threedimensional Triangulations | 68 |
References | 80 |
Machine Proofs of Geometry Theorems | 91 |
Wus Method and Its Variants | 97 |
Four Points | 169 |
A Final Touch for a Rigorous Proof | 179 |
Lower Bounds of P for the Rectilinear Metric | 186 |
Voronoi Diagrams and Delaunay Triangulations | 193 |
Properties of the Voronoi Diagram and Delaunay Triangulation | 205 |
Definitions from the Theory of Polyhedra | 228 |
Polar Forms and Triangular BSpline Surfaces | 235 |
Triangular Bézier Patches | 242 |
Algebraic vs Traditional Proofs | 108 |
Randomized Geometric Algorithms | 117 |
Sharper Expected Bounds for DivideandConquer | 126 |
Randomized Incremental Algorithms | 132 |
Some Combinatorial Bounds | 141 |
Still Sharper Bounds for DivideandConquer | 147 |
Reweighting Methods | 150 |
References | 157 |
The State of Art on Steiner Ratio Problems | 163 |
BPatches | 255 |
Bivariate BSplines | 263 |
References | 281 |
Computational Geometry and Topological Network Design | 287 |
Computational Geometry | 294 |
Paradigms and Geometric Data Structures | 299 |
Geometric TND Problems | 319 |
References | 371 |
Other editions - View all
Common terms and phrases
algebraic angle approach B-patch B-splines Bézier patch boundary cells CH(Z circle circumsphere complexity Computational Geometry Computer Science construction contains convex hull convex polygons defined Delaunay triangulation denote dimensions divide-and-conquer domain DT(Z Edelsbrunner edge length EMST endpoints ESPO Euclidean example face facets Figure flip geometric data structures geometric TND problems given halfspaces heuristic Hwang input points insertion interior intersection Lemma line segments linear lower bound mesh method minimum spanning tree node nonobtuse triangulation number of Steiner O(n log O(n² O(n³ O(nlogn obstacles optimal triangulation paradigms partition planar plane point set polyhedron polynomial Proc proof prove PSLG quadtree query random subset rectilinear region regular points shortest path simple polygon simplex solution solved space Steiner minimal tree Steiner points Steiner ratio subdivision surface Symp tetrahedra topology trapezoidal diagram tree problem triangular vector vertex vertices visibility graph Voronoi diagram Z-points