Algorithms in Combinatorial Geometry

Cover
Springer Science & Business Media, 31.07.1987 - 423 Seiten
0 Rezensionen
Computational geometry as an area of research in its own right emerged in the early seventies of this century. Right from the beginning, it was obvious that strong connections of various kinds exist to questions studied in the considerably older field of combinatorial geometry. For example, the combinatorial structure of a geometric problem usually decides which algorithmic method solves the problem most efficiently. Furthermore, the analysis of an algorithm often requires a great deal of combinatorial knowledge. As it turns out, however, the connection between the two research areas commonly referred to as computa tional geometry and combinatorial geometry is not as lop-sided as it appears. Indeed, the interest in computational issues in geometry gives a new and con structive direction to the combinatorial study of geometry. It is the intention of this book to demonstrate that computational and com binatorial investigations in geometry are doomed to profit from each other. To reach this goal, I designed this book to consist of three parts, acorn binatorial part, a computational part, and one that presents applications of the results of the first two parts. The choice of the topics covered in this book was guided by my attempt to describe the most fundamental algorithms in computational geometry that have an interesting combinatorial structure. In this early stage geometric transforms played an important role as they reveal connections between seemingly unrelated problems and thus help to structure the field.
 

Was andere dazu sagen - Rezension schreiben

Es wurden keine Rezensionen gefunden.

Ausgewählte Seiten

Inhalt

FUNDAMENTAL CONCEPTS IN COMBINATORIAL GEOMETRY
3
11 Arrangements of Hyperplanes
4
12 Counting Faces and Incidences
6
13 Combinatorial Equivalence
10
14 Configurations of Points
12
15 Sylvesters Problem
15
16 Convex Polytopes and Convex Polyhedra
16
17 Zonotopes
20
93 Constructing a Skeleton in a Simple Arrangement
183
94 Simulating Simplicity
185
941 A Conceptual Perturbation
186
942 Simulating the Perturbation
188
943 Computing the Sign of a Determinant of Polynomials
190
95 Penetration Search and Extremal Queries
192
951 Extremal Queries in the Plane
193
the Data Structure
195

18 Voronoi Diagrams
23
19 Exercises and Research Problems
25
110 Bibliographic Notes
27
PERMUTATION TABLES
29
22 Encoding Arrangements and Configurations
32
23 A Circularly NonRealizable 5Sequence
35
24 Arrangements of Pseudo Lines
37
25 Some Combinatorial Problems in the Plane
39
26 Exercises and Research Problems
41
27 Bibliographic Notes
44
SEMISPACES OF CONFIGURATIONS
45
31 Semispaces and Arrangements
46
32 kSets and Levels in Arrangements
47
33 A Lower Bound on the Number of Bisections in the Plane
50
34 Lower Bounds on the Number of kSets in the Plane
52
35 Extensions to Three and Higher Dimensions
54
36 Semispaces and Circular Sequences
55
37 An Upper Bound on the Number of kSets in the Plane
58
38 Exercises and Research Problems
60
39 Bibliographic Notes
61
DISSECTIONS OF POINT SETS
63
42 HamSandwich Cuts
66
43 Erasing Subdivisions in the Plane
70
44 Simultaneous FourSection in Three Dimensions
73
45 Erasing Cell Complexes in Three Dimensions
77
46 Generalizations to Higher Dimensions
78
47 Exercises and Research Problems
79
48 Bibliographic Notes
81
ZONES IN ARRANGEMENTS
83
51 Supported Cells Zones and Duality
84
52 Sweeping a Simple Arrangement
86
53 Tight Bounds in the Plane
89
54 Asymptotically Tight Bounds in d Dimensions
93
55 An Implication of the Result on Zones
94
56 Exercises and Research Problems
95
57 Bibliographic Notes
96
THE COMPLEXITY OF FAMILIES OF CELLS
97
61 Definitions and Preliminary Results
98
62 The Complexity of a Polytope
99
621 Cyclic Polytopes
100
622 Eulers Relation
102
623 The DehnSommerville Relations
104
624 An Asymptotic Version of the Upper Bound Theorem
106
63 The Complexity of a Few Cells in Two Dimensions
107
64 Lower Bounds for Moderately Many Cells
109
65 Lower Bounds for Many Cells
111
66 Upper Bounds for Many Cells
114
67 Exercises and Research Problems
116
68 Bibliographic Notes
118
FUNDAMENTAL GEOMETRIC ALGORITHMS
121
CONSTRUCTING ARRANGEMENTS
123
72 The Incremental Approach
125
73 Initiating the Construction
126
74 Geometric Preliminaries
128
75 Incrementing the Arrangement
130
76 The Analysis of the Algorithm
134
77 Exercises and Research Problems
136
78 Bibliographic Notes
137
CONSTRUCTING CONVEX HULLS
139
81 Convex Hulls and Duality
140
82 The Incidence Graph of a Convex Polytope
141
83 Two Algorithms in Two Dimensions
142
831 The BeneathBeyond Method
143
832 Using DivideandConquer
145
84 The BeneathBeyond Method in d Dimensions
147
841 Geometric Preliminaries
148
842 Towards the Incrementation of the Convex Hull
152
843 Pyramidal Updates
153
844 NonPyramidal Updates
154
845 The Analysis of the Algorithm
156
85 DivideandConquer in Three Dimensions
158
851 Coping with Degenerate Cases
159
852 The Upgraded Incidence Graph
160
853 Geometric Preliminaries
162
854 Wrapping Two Convex Polytopes
167
855 The Analysis of the Algorithm
172
86 Exercises and Research Problems
173
87 Bibliographic Notes
175
SKELETONS IN ARRANGEMENTS
177
91 Skeletons and Eulerian Tours
178
92 Towards the Construction of a Skeleton
181
the Query Algorithm
201
954 Dynamic Extremal Search
202
96 Exercises and Research Problems
205
97 Bibliographic Notes
208
LINEAR PROGRAMMING
209
101 The Solution to a Linear Program
210
102 Linear Programming and Duality
212
103 Linear Programming in Two Dimensions
214
Eliminate Redundant HalfPlanes
215
Decrease the Range of the Linear Program
217
Determine the Median
219
1034 Assembling the Algorithm
220
104 Linear Programming in Three and Higher Dimensions
223
1041 The Geometry of Pruning
224
1042 The Geometry of Bisecting
225
1043 Searching Lines in the Plane
228
1044 The Geometry of Searching
230
1045 The Overall Algorithm
234
105 Exercises and Research Problems
236
106 Bibliographic Notes
238
PLANAR POINT LOCATION SEARCH
241
111 Eulers Relation for Planar Graphs
242
112 The Geometry of Monotone Subdivisions
244
113 A Tree of Separators for Point Location
248
114 Representing a Plane Subdivision
251
115 Constructing a Family of Separators
252
116 Optimal Search by Connecting Separators
256
117 Constructing the Layered DAG
258
118 Refining NonMonotone Subdivisions
260
119 Exercises and Research Problems
262
1110 Bibliographic Notes
265
GEOMETRIC AND ALGORITHMIC APPLICATIONS
269
PROBLEMS FOR CONFIGURATIONS AND ARRANGEMENTS
271
121 Largest Convex Subsets
272
122 The Visibility Graph for Line Segments
275
123 Degeneracies in Configurations
278
124 Minimum Measure Simplices
282
Sorting in d Dimensions?
284
126 A VectorSum Maximization Problem
286
127 Exercises and Research Problems
288
128 Bibliographic Notes
290
VORONOI DIAGRAMS
293
131 Classical Voronoi Diagrams
294
132 Applications in the Plane
298
1322 Triangulating Point Sets
299
1323 Delaunay Triangulations from Convex Hulls
303
1324 Finding Closest Neighbors
306
1326 Shapes of Point Sets
309
133 HigherOrder Voronoi Diagrams
315
134 The Complexity of HigherOrder Voronoi Diagrams
319
135 Constructing HigherOrder Voronoi Diagrams
324
136 Power Diagrams
327
137 Exercises and Research Problems
328
138 Bibliographic Notes
332
SEPARATION AND INTERSECTION IN THE PLANE
335
141 Constructing HamSandwich Cuts in Two Dimensions
336
1412 Testing a Line
339
1413 Finding Test Lines and Pruning
341
1414 The Overall Algorithm
343
142 Answering Line Queries
345
1422 Point Location in Arrangements
348
143 A SelfDual Intersection Problem
349
144 Triangular Range Queries
351
145 Exercises and Research Problems
354
146 Bibliographic Notes
356
PARADIGMATIC DESIGN OF ALGORITHMS
359
152 Geometric Transformation
361
153 Combinatorial Analysis
363
154 DivideandConquer
365
155 Incremental Construction
367
156 PruneandSearch
370
157 The Locus Approach
371
158 Dynamization by Decomposition
373
159 Exercises and Research Problems
376
1510 Bibliographic Notes
378
REFERENCES
381
DEFINITIONS
395
NOTATIONAL CONVENTIONS
409
INDEX
417
Urheberrecht

Andere Ausgaben - Alle anzeigen

Häufige Begriffe und Wortgruppen

Beliebte Passagen

Seite ii - Petri Nets. An Introduction. X, 161 pages, 111 figs. 1985. Vol. 5: W. Kuich, A. Salomaa: Semirings, Automata, Languages. IX, 374 pages, 23 figs. 1986. Vol. 6: H. Ehrig, B. Mahr: Fundamentals of Algebraic Specification 1. Equations and Initial Semantics. XI, 321 pages. 1985.
Seite vii - ... fundamental algorithms in computational geometry that have an interesting combinatorial structure. In this early stage geometric transforms played an important role as they reveal connections between seemingly unrelated problems and thus help to structure the field. These transforms led me to believe that arrangements of hyperplanes are at the very heart of computational geometry - and this is my belief now more than ever.
Seite 382 - A recursive sweep-plane algorithm, determining all cells of a finite division of Rd , Computing 28 , pp.189-198, 1982.

Verweise auf dieses Buch

Alle Ergebnisse von Google Books »

Bibliografische Informationen