| Preface | |
| On the Development of Quantitative Geometry from Pythagoras to Grassmann | p. 1 |
| Introduction | p. 1 |
| Foundation of Quantitative Geometry | p. 2 |
| Commensurability and non-commensurability | p. 3 |
| The area formula of rectangles, Pythagoras theorem and the similar triangle theorem | p. 3 |
| Euclidean trigonometry | p. 5 |
| Foundation of Analytic (Vector) Geometry | p. 6 |
| Displacement vectors | p. 6 |
| Oriented volume and high dimensional inner product | p. 10 |
| The Grassmann algebra | p. 12 |
| Some Applications | p. 15 |
| Spherical trigonometry and spherical geometry | p. 15 |
| A volume formula of superscribing polyhedrons | p. 19 |
| References | p. 20 |
| Mesh Generation and Optimal Triangulation | p. 23 |
| Introduction | p. 23 |
| Background | p. 24 |
| Formulating the problems | p. 25 |
| Organization | p. 26 |
| Two-dimensional Triangulations | p. 27 |
| Triangulation without optimization | p. 28 |
| Optimal triangulation | p. 29 |
| Steiner triangulation | p. 43 |
| Heuristically generated meshes | p. 57 |
| Two-and-a-half-dimensional problems | p. 63 |
| Three-dimensional Triangulations | p. 68 |
| Tetrahedralization without optimization | p. 68 |
| Optimal tetrahedralization | p. 72 |
| Steiner tetrahedralization | p. 75 |
| Heuristically generated three-dimensional meshes | p. 78 |
| Conclusions | p. 80 |
| References | p. 80 |
| Machine Proofs of Geometry Theorems | p. 91 |
| Introduction | p. 91 |
| History of Automated Theorem Proving | p. 92 |
| Traditional Proofs | p. 94 |
| Algebraic Proofs | p. 96 |
| Wu's Method and Its Variants | p. 97 |
| Grobner basis method | p. 105 |
| Algebraic v/s Traditional Proofs | p. 108 |
| Axiomatic geometries and number systems | p. 108 |
| Algebraic proofs v/s formal proofs | p. 111 |
| Concluding Remarks | p. 111 |
| References | p. 112 |
| Randomized Geometric Algorithms | p. 117 |
| Introduction | p. 117 |
| Outline | p. 118 |
| Probabilistic Divide-and-Conquer | p. 119 |
| Closest-point queries | p. 119 |
| The Vapnik-Chervonenkis dimension | p. 123 |
| Sharper Expected Bounds for Divide-and-Conquer | p. 126 |
| Trapezoidal diagrams of simple polygons | p. 126 |
| Proving the expected bounds | p. 129 |
| General segments and lines | p. 131 |
| Randomized Incremental Algorithms | p. 132 |
| Convex hulls | p. 132 |
| Analysis of insertions | p. 135 |
| Other search schemes | p. 138 |
| Trapezoidal diagrams and planar point location | p. 140 |
| Some Combinatorial Bounds | p. 141 |
| Incidences | p. 141 |
| Bounds on [actual symbol not reproducible]-regions | p. 144 |
| Still Sharper Bounds for Divide-and-Conquer | p. 147 |
| Bounds for the sum of squares | p. 148 |
| Uniform bounds and cuttings | p. 149 |
| Reweighting Methods | p. 150 |
| Linear programming | p. 150 |
| Triangular partitions | p. 152 |
| Closing Remarks | p. 154 |
| Appendix A. Some Probability, Geometry, and Notation | p. 154 |
| Appendix B. | p. 155 |
| References | p. 157 |
| The State of Art on Steiner Ratio Problems | p. 163 |
| Introduction | p. 163 |
| Background of the [actual symbol not reproducible] Conjecture | p. 164 |
| A Minimax Theorem | p. 166 |
| Four Points | p. 169 |
| Minimum Hexagonal Trees | p. 172 |
| Inner Spanning Trees | p. 174 |
| A Final Touch for a Rigorous Proof | p. 179 |
| A Background of the Better Heuristics Problem | p. 181 |
| A Better Heuristic for an Arbitrary Metric Space | p. 182 |
| Lower Bounds of Q[subscript k] | p. 184 |
| Lower Bounds of [rho [subscript k]] for the Rectilinear Metric | p. 186 |
| Open Problems | p. 188 |
| References | p. 189 |
| Voronoi Diagrams and Delaunay Triangulations | p. 193 |
| Introduction | p. 193 |
| Definition of the Voronoi Diagram and Delaunay Triangulation | p. 197 |
| Voronoi diagrams and Delaunay triangulations | p. 197 |
| Connection with convex polyhedra | p. 200 |
| Combinatorial complexity | p. 203 |
| Properties of the Voronoi Diagram and Delaunay Triangulation | p. 205 |
| Optimality of the Delaunay triangulation | p. 205 |
| Geometric graph properties | p. 206 |
| Inscribability | p. 207 |
| Algorithms | p. 209 |
| Primitives for Delaunay triangulation algorithms | p. 210 |
| Flipping | p. 212 |
| The incremental algorithm | p. 214 |
| The random incremental algorithm | p. 217 |
| The plane-sweep algorithm | p. 220 |
| Other algorithms | p. 223 |
| The real RAM and the general position assumption | p. 223 |
| Implementation issues | p. 226 |
| Appendix 1. Definitions from the Theory of Polyhedra | p. 228 |
| Appendix 2. Proof of Theorem 2.1 | p. 229 |
| References | p. 230 |
| Polar Forms and Triangular B-Spline Surfaces | p. 235 |
| Introduction | p. 235 |
| Polynomials and Polar Forms | p. 237 |
| Triangular Bezier Patches | p. 242 |
| The Bernstein-Bezier Representation | p. 242 |
| The de Casteljau algorithm and its applications | p. 247 |
| B-Patches | p. 255 |
| The B-patch representation | p. 255 |
| The de Boor algorithm and its applications | p. 257 |
| Bivariate B-Splines | p. 263 |
| A New B-Spline Scheme | p. 267 |
| A new spline space | p. 267 |
| Representing piecewise polynomials as linear combinations of B-splines | p. 274 |
| Properties of the new B-spline scheme | p. 277 |
| References | p. 281 |
| Computational Geometry and Topological Network Design | p. 287 |
| Introduction | p. 288 |
| Purpose and focus | p. 288 |
| Overview of the survey | p. 288 |
| Network Design Problems | p. 289 |
| Topological network design | p. 291 |
| Routing network design | p. 292 |
| Capacitated network design | p. 292 |
| Geometric topological network design | p. 293 |
| TND definitions and assumptions | p. 293 |
| Computational Geometry | p. 294 |
| Mathematical programming vs. geometric approaches | p. 296 |
| Combinatorial optimization vs. geometric approaches | p. 298 |
| Easy vs. difficult problems | p. 298 |
| Paradigms and Geometric Data Structures | p. 299 |
| Paradigms | p. 299 |
| Geometric data structures | p. 305 |
| Geometric TND Problems | p. 319 |
| G(Z) problems | p. 320 |
| G(E) problems | p. 333 |
| G(Z,E) problems | p. 344 |
| G(Omega) problems | p. 353 |
| [Actual symbol not reproducible] cube | p. 361 |
| Composite matrix | p. 365 |
| Planar graph diagram | p. 365 |
| [Actual symbol not reproducible] decomposition | p. 367 |
| Open problems | p. 369 |
| Summary and Conclusions | p. 369 |
| References | p. 371 |
| Table of Contents provided by Blackwell. All Rights Reserved. |
