Triangulations and Applications

Front Cover
Springer Science & Business Media, Sep 19, 2006 - Mathematics - 229 pages
0 Reviews
This book is entirely about triangulations. With emphasis on computational issues, we present the basic theory necessary to construct and manipulate triangulations. In particular, we make a tour through the theory behind the Delaunay triangulation, including algorithms and software issues. We also discuss various data structures used for the representation of triangulations. Throughout the book we relate the theory to selected applications, in part- ular surface construction, meshing and visualization. The ?eld of triangulation is part of the huge area of computational ge- etry, and over many years numerous books and articles have been written on the subject. Important results on triangulations have appeared in theore- cal books and articles, mostly within the realm of computational geometry. However, many important results on triangulations have also been presented in publications within other research areas, where they have played and play an important role in solving speci?c scienti?c and applied problems. We will touch upon some of these areas in this book. Triangulations, almost everywhere. The early development of triangulation comes from surveying and the art of constructing maps – cartography. S- veyors and cartographers used triangles as the basic geometric feature for calculating distances between points on the Earth’s surface and a position’s elevation above sea level.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Triangles and Triangulations
1
12 Triangulations
5
13 Some Properties of Triangulations
7
14 A Triangulation Algorithm
10
15 Edge Insertion
16
16 Using Triangulations
18
17 Exercises
20
Graphs and Data Structures
23
56 Modified Local Optimization Procedures MLOP
106
58 Exercises
112
Constrained Delaunay Triangulation
113
62 Generalization of Delaunay Triangulation
115
63 Algorithms for Constrained Delaunay Triangulation
118
64 Inserting an Edge into a CDT
119
65 Edge Insertion and Swapping
123
66 Inserting a Point into a CDT
127

22 Generalized Maps Gmaps
25
23 Data Structures for Triangulations
29
24 A Minimal TriangleBased Data Structure
31
25 TriangleBased Data Structure with Neighbors
32
26 VertexBased Data Structure with Neighbors
33
27 HalfEdge Data Structure
35
28 DartBased Data Structure
37
29 Triangles for Visualization
38
210 Binary Triangulations
41
211 Exercises
45
Delaunay Triangulations and Voronoi Diagrams
46
32 The Neutral Case
50
33 Voronoi Diagrams
51
34 Delaunay Triangulation as the Dual of the Voronoi Diagram
54
35 The Circle Criterion
57
36 Equivalence of the Delaunay Criteria for Strictly Convex Quadrilaterals
59
37 Computing the Circumcircle Test
62
38 The Local Optimization Procedure LOP
64
39 Global Properties of the Delaunay Triangulation
66
310 Exercises
71
Algorithms for Delaunay Triangulation
73
42 Radial Sweep
74
43 A StepbyStep Approach for Making Delaunay Triangles
75
44 Incremental Algorithms
78
45 Inserting a Point into a Delaunay Triangulation
79
46 Point Insertion and EdgeSwapping
81
47 Running Time of Incremental Algorithms
87
48 DivideandConquer
89
49 Exercises
92
Data Dependent Triangulations
94
52 Optimal Triangulations Revisited
96
53 The General Concept
98
54 Data Dependent Swapping Criteria
101
55 On Implementation of the LOP
105
67 Exercises
129
Delaunay Refinement Mesh Generation
131
72 General Requirements for Meshes
132
73 Node Insertion
134
74 Splitting Encroached Segments
139
75 The Delaunay Refinement Algorithm
142
76 Minimum Edge Length and Termination
145
77 CornerLopping for Handling Small Input Angles
152
78 Spatial Grading
154
Least Squares Approximation of Scattered Data
156
82 Approximation over Triangulations of Subsets of Data
160
83 Existence and Uniqueness
163
84 Sparsity and Symmetry
164
85 Penalized Least Squares
166
86 Smoothing Terms for Penalized Least Squares
168
87 Approximation over General Triangulations
175
88 Weighted Least Squares
178
89 Constrained Least Squares
180
810 Approximation over Binary Triangulations
182
811 Numerical Examples for Binary Triangulations
185
812 Exercises
191
Programming Triangulations The Triangulation Template Library TTL
193
91 Implementation of the HalfEdge Data Structure
194
92 The Overall Design and the Adaptation Layer
197
93 Topological Queries and the Dart Class
199
94 Some Iterator Classes
203
95 Geometric Queries and the Traits Class
205
96 Geometric and Topological Modifiers
211
97 Generic Delaunay Triangulation
213
98 Exercises
221
References
223
Index
229
Copyright

Other editions - View all

Common terms and phrases