دانلود کتاب Algorithms in Combinatorial Geometry

عنوان فارسی :

دانلود کتاب الگوریتم های هندسه ترکیبی

عنوان انگلیسی :

Algorithms in Combinatorial Geometry

زبان : English

موضوع : Mathematics->Discrete Mathematics

نویسندگان : Herbert Edelsbrunner

ناشر : Springer

ISBN (شابک) : 9783540137221, 354013722X, 038713722X, 9780387137223

تعداد صفحات : 439\439

سال نشر : 1987     ویرایش :

حجم : 5 MB       فرمت : djvu

قیمت : 20000 تومان

فهرست :



Table of contents :
Cover......Page 1
Series......Page 2
Title page......Page 3
Date-line......Page 4
Dedication......Page 5
Preface......Page 7
TABLE OF CONTENTS......Page 11
PART I COMBINATORIAL GEOMETRY......Page 17
CHAPTER 1 Fundamental Concepts in Combinatorial Geometry......Page 19
1.1. Arrangements of Hyperplanes......Page 20
1.2. Counting Faces and Incidences......Page 22
1.3. Combinatorial Equivalence......Page 26
1.4. Configurations of Points......Page 28
1.5. Sylvester's Problem......Page 31
1.6. Convex Polytopes and Convex Polyhedra......Page 32
1.7. Zonotopes......Page 36
1.8. Voronoi Diagrams......Page 39
1.9. Exercises and Research Problems......Page 41
1.10. Bibliographic Notes......Page 43
2.1. Circular Sequences......Page 45
2.2. Encoding Arrangements and Configurations......Page 48
2.3. A Circularly Non-Realizable 5-Sequence......Page 51
2.4. Arrangements of Pseudo-Lines......Page 53
2.5. Some Combinatorial Problems in the Plane......Page 55
2.6. Exercises and Research Problems......Page 57
2.7. Bibliographic Notes......Page 60
CHAPTER 3 Semispaces of Configurations......Page 61
3.1. Semispaces and Arrangements......Page 62
3.2. $k$-Sets and Levels in Arrangements......Page 63
3.3. A Lower Bound on the Number of Bisections in the Plane......Page 66
3.4. Lower Bounds on the Number of $k$-Sets in the Plane......Page 68
3.5. Extensions to Three and Higher Dimensions......Page 70
3.6. Semispaces and Circular Sequences......Page 71
3.7. An Upper Bound on the Number of $k$-Sets in the Plane......Page 74
3.8. Exercises and Research Problems......Page 76
3.9. Bibliographic Notes......Page 77
4.1. Centerpoints......Page 79
4.2. Ham-Sandwich Cuts......Page 82
4.3. Erasing Subdivisions in the Plane......Page 86
4.4. Simultaneous Four-Section in Three Dimensions......Page 89
4.5. Erasing Cell Complexes in Three Dimensions......Page 93
4.6. Generalizations to Higher Dimensions......Page 94
4.7. Exercises and Research Problems......Page 95
4.8. Bibliographic Notes......Page 97
CHAPTER 5 Zones in Arrangements......Page 99
5.1. Supported Cells, Zones, and Duality......Page 100
5.2. Sweeping a Simple Arrangement......Page 102
5.3. Tight Bounds in the Plane......Page 105
5.4. Asymptotically Tight Bounds in $d$ Dimensions......Page 109
5.5. An Implication of the Result on Zones......Page 110
5.6. Exercises and Research Problems......Page 111
5.7. Bibliographic Notes......Page 112
CHAPTER 6 The Complexity of Families of Cells......Page 113
6.1. Definitions and Preliminary Results......Page 114
6.2. The Complexity of a Polytope......Page 115
6.2.1. Cyclic Polytopes......Page 116
6.2.2. Euler's Relation......Page 118
6.2.3. The Dehn-Sommerville Relations......Page 120
6.2.4. An Asymptotic Version of the Upper Bound Theorem......Page 122
6.3. The Complexity of a Few Cells in Two Dimensions......Page 123
6.4. Lower Bounds for Moderately Many Cells......Page 125
6.5. Lower Bounds for Many Cells......Page 127
6.6. Upper Bounds for Many Cells......Page 130
6.7. Exercises and Research Problems......Page 132
6.8. Bibliographic Notes......Page 134
PART II FUNDAMENTAL GEOMETRIC ALGORITHMS......Page 137
7.1. Representing an Arrangement in Storage......Page 139
7.2. The Incremental Approach......Page 141
7.3. Initiating the Construction......Page 142
7.4. Geometric Preliminaries......Page 144
7.5. Incrementing the Arrangement......Page 146
7.6. The Analysis of the Algorithm......Page 150
7.7. Exercises and Research Problems......Page 152
7.8. Bibliographic Notes......Page 153
CHAPTER 8 Constructing Convex Hulls......Page 155
8.1. Convex Hulls and Duality......Page 156
8.2. The Incidence Graph of a Convex Polytope......Page 157
8.3. Two Algorithms in Two Dimensions......Page 158
8.3.1. The Beneath-Beyond Method......Page 159
8.3.2. Using Divide-and-Conquer......Page 161
8.4. The Beneath-Beyond Method in $d$ Dimensions......Page 163
8.4.1. Geometric Preliminaries......Page 164
8.4.2. Towards the Incrementation of the Convex Hull......Page 168
8.4.3. Pyramidal Updates......Page 169
8.4.4. Non-Pyramidal Updates......Page 170
8.4.5. The Analysis of the Algorithm......Page 172
8.5. Divide-and-Conquer in Three Dimensions......Page 174
8.5.1. Coping with Degenerate Cases......Page 175
8.5.2. The Upgraded Incidence Graph......Page 176
8.5.3. Geometric Preliminaries......Page 178
8.5.4. Wrapping Two Convex Polytopes......Page 183
8.5.5. The Analysis of the Algorithm......Page 188
8.6. Exercises and Research Problems......Page 189
8.7. Bibliographic Notes......Page 191
CHAPTER 9 Skeletons in Arrangements......Page 193
9.1. Skeletons and Eulerian Tours......Page 194
9.2. Towards the Construction of a Skeleton......Page 197
9.3. Constructing a Skeleton in a Simple Arrangement......Page 199
9.4. Simulating Simplicity......Page 201
9.4.1. A Conceptual Perturbation......Page 202
9.4.2. Simulating the Perturbation......Page 204
9.4.3. Computing the Sign of a Determinant of Polynomials......Page 206
9.5. Penetration Search and Extremal Queries......Page 208
9.5.1. Extremal Queries in the Plane......Page 209
9.5.2. Extremal Queries in Three Dimensions: the Data Structure......Page 211
9.5.3. Extremal Queries in Three Dimensions: the Query Algorithm......Page 217
9.5.4. Dynamic Extremal Search......Page 218
9.6. Exercises and Research Problems......Page 221
9.7. Bibliographic Notes......Page 224
CHAPTER 10 Linear Programming......Page 225
10.1. The Solution to a Linear Program......Page 226
10.2. Linear Programming and Duality......Page 228
10.3. Linear Programming in Two Dimensions......Page 230
10.3.1. Prune: Eliminate Redundant Half-Planes......Page 231
10.3.2. Bisect: Decrease the Range of the Linear Program......Page 233
10.3.3. Find_Test: Determine the Median......Page 235
10.3.4. Assembling the Algorithm......Page 236
10.4. Linear Programming in Three and Higher Dimensions......Page 239
10.4.1. The Geometry of Pruning......Page 240
10.4.2. The Geometry of Bisecting......Page 241
10.4.3. Searching Lines in the Plane......Page 244
10.4.4. The Geometry of Searching......Page 246
10.4.5. The Overall Algorithm......Page 250
10.5. Exercises and Research Problems......Page 252
10.6. Bibliographic Notes......Page 254
CHAPTER 11 Planar Point Location Search......Page 257
11.1. Euler's Relation for Planar Graphs......Page 258
11.2. The Geometry of Monotone Subdivisions......Page 260
11.3. A Tree of Separators for Point Location......Page 264
11.4. Representing a Plane Subdivision......Page 267
11.5. Constructing a Family of Separators......Page 268
11.6. Optimal Search by Connecting Separators......Page 272
11.7. Constructing the Layered DAG......Page 274
11.8. Refining Non-Monotone Subdivisions'......Page 276
11.9. Exercises and Research Problems......Page 278
11.10. Bibliographic Notes......Page 281
PART III GEOMETRIC AND ALGORITHMIC APPLICATIONS......Page 285
CHAPTER 12 Problems for Configurations and Arrangements......Page 287
12.1. Largest Convex Subsets......Page 288
12.2. The Visibility Graph for Line Segments......Page 291
12.3. Degeneracies in Configurations......Page 294
12.4. Minimum Measure Simplices......Page 298
12.5. Computing Ranks: Sorting in $d$ Dimensions?......Page 300
12.6. A Vector-Sum Maximization Problem......Page 302
12.7. Exercises and Research Problems......Page 304
12.8. Bibliographic Notes......Page 306
CHAPTER 13 Voronoi Diagrams......Page 309
13.1. Classical Voronoi Diagrams......Page 310
13.2.1. The Post Office Problem......Page 314
13.2.2. Triangulating Point Sets......Page 315
13.2.3. Delaunay Triangulations from Convex Hulls......Page 319
13.2.5. Minimum Spanning Trees......Page 322
13.2.6. Shapes of Point Sets......Page 325
13.3. Higher-Order Voronoi Diagrams......Page 331
13.4. The Complexity of Higher-Order Voronoi Diagrams......Page 335
13.5. Constructing Higher-Order Voronoi Diagrams......Page 340
13.6. Power Diagrams......Page 343
13.7. Exercises and Research Problems......Page 344
13.8. Bibliographic Notes......Page 348
CHAPTER 14 Separation and Intersection in the Plane......Page 351
14.1.1. Ham-Sandwich Cuts and Duality......Page 352
14.1.2. Testing a Line......Page 355
14.1.3. Finding Test Lines and Pruning......Page 357
14.1.4. The Overall Algorithm......Page 359
14.2.1. The Ham-Sandwich Tree......Page 361
14.2.2. Point Location in Arrangements......Page 364
14.3. A Self-Dual Intersection Problem......Page 365
14.4. Triangular Range Queries......Page 367
14.5. Exercises and Research Problems......Page 370
14.6. Bibliographic Notes......Page 372
15.1. The Problem: Stabbing Line Segments in the Plane......Page 375
15.2. Geometric Transformation......Page 377
15.3. Combinatorial Analysis......Page 379
15.4. Divide-and-Conquer......Page 381
15.5. Incremental Construction......Page 383
15.6. Prune-and-Search......Page 386
15.7. The Locus Approach......Page 387
15.8. Dynamization by Decomposition......Page 389
15.9. Exercises and Research Problems......Page 392
15.10. Bibliographic Notes......Page 394
REFERENCES......Page 397
APPENDIX A Definitions......Page 411
APPENDIX B Notational Conventions......Page 425
INDEX......Page 433





کتاب های پزشکی

دانلود کتاب Casarett and Doull's toxicology: the basic science of poisons Sixth Edition

دانلود کتاب Encyclopedia of molecular mechanisms of disease

دانلود کتاب Vitamin D, 3rd Edition (2-Volume Set)

دانلود کتاب Atlas of Forensic Medicine. CD-ROM.

دانلود کتاب Analytical techniques for biopharmaceutical development

کتاب های کامپیوتر

دانلود کتاب IPhone SDK 3 Programming: Advanced Mobile Development for Apple IPhone and IPod Touch

دانلود کتاب Head First iPhone Development: A Learner's Guide to Creating Objective-C Applications for the iPhone

دانلود کتاب HTML, XHTML and CSS All-In-One For Dummies, 2nd Edition

دانلود کتاب Oracle E-Business Suite 12 Financials Cookbook

دانلود کتاب Practical C programming

کتاب های ریاضی

دانلود کتاب Industrial Control Systems: Advances and Applications, First Edition (Repost)

دانلود کتاب Fundamentals of Probability (2nd Edition)

دانلود کتاب Mathematics for the Trades: A Guided Approach

دانلود کتاب Some Problems on Nonlinear Hyperbolic Equations and Applications (Series in Contemporary Applied Mathematics)

دانلود کتاب Set Theory, Arithmetic, and Foundations of Mathematics: Theorems, Philosophies

کتاب های تکنولوژی

دانلود کتاب Design and Analysis of Composite Structures: With Applications to Aerospace Structures

دانلود کتاب RNA-Protein Interaction Protocols

دانلود کتاب Microcontrollers in Practice

دانلود کتاب Industrial Sprays and Atomization: Design, Analysis and Applications

دانلود کتاب Popular Woodworking - Complete Book of Tips, Tricks & Techniques

کتاب های مذهبی

دانلود کتاب Emperor Worship and Roman Religion (Oxford Classical Monographs)

دانلود کتاب Slavery, Sabbath, War and Women: Case Issues in Biblical Interpretation (Conrad Grebel Lecture)

دانلود کتاب New Testament Introduction

دانلود کتاب Heart of Islam, The: Enduring Values for Humanity

دانلود کتاب The Dead Sea Scrolls and the Personages of Earliest Christianity

کتاب های فیزیولوژی

دانلود کتاب Therapielexikon Psychiatrie, Psychosomatik, Psychotherapie

دانلود کتاب The Psychology of Strategic Terrorism: Public and Government Responses to Attack

دانلود کتاب MAT: Power Practice

دانلود کتاب Psychologische Begutachtung im Strafverfahren: Indikationen, Methoden, Qualitätsstandards

دانلود کتاب Kama Sutra 365

کتاب های تاریخی

دانلود کتاب Ancient Greece (Grades 4-8)

دانلود کتاب VIII Fighter Command at War

دانلود کتاب Algeria Since 1989: Between Terror and Democracy (Global History of the Present)

دانلود کتاب Stuka Volume Two: Luftwaffe Ju 87 Dive-Bomber Units 1942-1945 (Luftwaffe Colours)

دانلود کتاب Sukhoi Su-7/-17/-20/-22

کتاب های زیست شناسی

دانلود کتاب Antropologia culturale

دانلود کتاب Elite Cultures: Anthropological Perspectives

دانلود کتاب Evolutionary History of the Primates

دانلود کتاب Recent Advances in Human Retroviruses: Principles of Replication and Pathogenesis - Advances in Retroviral Research

دانلود کتاب Mechanobiology Handbook

کتاب های اقتصاد

دانلود کتاب Business Communication for Success

دانلود کتاب Inside Marketing: Practices, Ideologies, Devices

دانلود کتاب Analog Integrated Circuits-Power management Signal conditioning and ASSP

دانلود کتاب

دانلود کتاب Marketing: Real People, Real Choices, 7th Edition

کتاب های آموزشی

دانلود کتاب Effective Teaching with Internet Technologies: Pedagogy and Practice

دانلود کتاب Animals and Me

دانلود کتاب Teach Yourself Visually Sock Knitting

دانلود کتاب Cold War: A Student Encyclopedia

دانلود کتاب Occupying Architecture

کتاب های حقوق

دانلود کتاب Law and Society in Vietnam: The Transition from Socialism in Comparative Perspective

دانلود کتاب McMafia: a journey through the global criminal underworld

دانلود کتاب Darfur and the crime of genocide

دانلود کتاب Lawrence and the Arab Revolts

دانلود کتاب Memory, Imagination, Justice: Intersections of Law and Literature

کتاب های علوم انسانی

دانلود کتاب Process and Reality: An Essay in Cosmology

دانلود کتاب Cultures and Organizations: Software for the Mind, Third Edition

دانلود کتاب New Illustrated Treasury of Disney Songs

دانلود کتاب The Fragility of Goodness: Luck and Ethics in Greek Tragedy and Philosophy

دانلود کتاب Social and Personality Development , Sixth Edition