عنوان

Algorithms in combinatorial geometry

شابک

3642615686

شابک

3642648738

شابک

9783642615689

شابک

9783642648731

شماره

b571822

عنوان اصلي

Algorithms in combinatorial geometry

نام عام مواد

[Book]

نام نخستين پديدآور

Herbert Edelsbrunner.

محل نشرو پخش و غیره

Berlin

نام ناشر، پخش کننده و غيره

Springer-Verlag, [post

تاریخ نشرو بخش و غیره

2005], cop. 1987.

نام خاص و کميت اثر

XV, [1], 423 s. : il. ; 24 cm.

عنوان فروست

EATCS Monographs on Theoretical Computer Science, vol. 10.

متن يادداشت

Na dok. data cop. 1987, data ustalona na podst 13-ISBN: [post 2005].

متن يادداشت

I Combinatorial Geometry.- 1 Fundamental Concepts in Combinatorial Geometry.- 1.1. Arrangements of Hyperplanes.- 1.2. Counting Faces and Incidences.- 1.3. Combinatorial Equivalence.- 1.4. Configurations of Points.- 1.5. Sylvester's Problem.- 1.6. Convex Polytopes and Convex Polyhedra.- 1.7. Zonotopes.- 1.8. Voronoi Diagrams.- 1.9. Exercises and Research Problems.- 1.10. Bibliographic Notes.- 2 Permutation Tables.- 2.1. Circular Sequences.- 2.2. Encoding Arrangements and Configurations.- 2.3. A Circularly Non-Realizable 5-Sequence.- 2.4. Arrangements of Pseudo-Lines.- 2.5. Some Combinatorial Problems in the Plane.- 2.6. Exercises and Research Problems.- 2.7. Bibliographic Notes.- 3 Semispaces of Configurations.- 3.1. Semispaces and Arrangements.- 3.2. k-Sets and Levels in Arrangements.- 3.3. A Lower Bound on the Number of Bisections in the Plane.- 3.4. Lower Bounds on the Number of k-Sets in the Plane.- 3.5. Extensions to Three and Higher Dimensions..- 3.6. Semispaces and Circular Sequences.- 3.7. An Upper Bound on the Number of k-Sets in the Plane.- 3.8. Exercises and Research Problems.- 3.9. Bibliographic Notes.- 4 Dissections of Point Sets.- 4.1. Centerpoints.- 4.2. Ham-Sandwich Cuts.- 4.3. Erasing Subdivisions in the Plane.- 4.4. Simultaneous Four-Section in Three Dimensions.- 4.5. Erasing Cell Complexes in Three Dimensions.- 4.6. Generalizations to Higher Dimensions.- 4.7. Exercises and Research Problems.- 4.8. Bibliographic Notes.- 5 Zones in Arrangements.- 5.1. Supported Cells, Zones, and Duality.- 5.2. Sweeping a Simple Arrangement.- 5.3. Tight Bounds in the Plane.- 5.4. Asymptotically Tight Bounds in d Dimensions.- 5.5. An Implication of the Result on Zones.- 5.6. Exercises and Research Problems.- 5.7. Bibliographic Notes.- 6 The Complexity of Families of Cells.- 6.1. Definitions and Preliminary Results.- 6.2. The Complexity of a Polytope.- 6.2.1. Cyclic Polytopes.- 6.2.2. Euler's Relation.- 6.2.3. The Dehn-Sommerville Relations.- 6.2.4. An Asymptotic Version of the Upper Bound Theorem.- 6.3. The Complexity of a Few Cells in Two Dimensions.- 6.4. Lower Bounds for Moderately Many Cells.- 6.5. Lower Bounds for Many Cells.- 6.6. Upper Bounds for Many Cells.- 6.7. Exercises and Research Problems.- 6.8. Bibliographic Notes.- II Fundamental Geometric Algorithms.- 7 Constructing Arrangements.- 7.1. Representing an Arrangement in Storage.- 7.2. The Incremental Approach.- 7.3. Initiating the Construction.- 7.4. Geometric Preliminaries.- 7.5. Incrementing the Arrangement.- 7.6. The Analysis of the Algorithm.- 7.7. Exercises and Research Problems.- 7.8. Bibliographie Notes.- 8 Constructing Convex Hulls.- 8.1. Convex Hulls and Duality.- 8.2. The Incidence Graph of a Convex Polytope.- 8.3. Two Algorithms in Two Dimensions.- 8.3.1. The Beneath-Beyond Method.- 8.3.2. Using Divide-and-Conquer.- 8.4. The Beneath-Beyond Method in d Dimensions.- 8.4.1. Geometric Preliminaries.- 8.4.2. Towards the Incrementation of the Convex Hull.- 8.4.3. Pyramidal Updates.- 8.4.4. Non-Pyramidal Updates.- 8.4.5. The Analysis of the Algorithm.- 8.5. Divide-and-Conquer in Three Dimensions.- 8.5.1. Coping with Degenerate Cases.- 8.5.2. The Upgraded Incidence Graph.- 8.5.3. Geometric Preliminaries.- 8.5.4. Wrapping Two Convex Polytopes.- 8.5.5. The Analysis of the Algorithm.- 8.6. Exercises and Research Problems.- 8.7. Bibliographic Notes.- 9 Skeletons in Arrangements.- 9.1. Skeletons and Eulerian Tours.- 9.2. Towards the Construction of a Skeleton.- 9.3. Constructing a Skeleton in a Simple Arrangement.- 9.4. Simulating Simplicity.- 9.4.1. A Conceptual Perturbation.- 9.4.2. Simulating the Perturbation.- 9.4.3. Computing the Sign of a Determinant of Polynomials..- 9.5. Penetration Search and Extremal Queries.- 9.5.1. Extremal Queries in the Plane.- 9.5.2. Extremal Queries in Three Dimensions: the Data Structure.- 9.5.3. Extremal Queries in Three Dimensions: the Query Algorithm.- 9.5.4. Dynamic Extremal Search.- 9.6. Exercises and Research Problems.- 9.7. Bibliographic Notes.- 10 Linear Programming..- 10.1. The Solution to a Linear Program.- 10.2. Linear Programming and Duality.- 10.3. Linear Programming in Two Dimensions.- 10.3.1. Prune: Eliminate Redundant Half-Planes.- 10.3.2. Bisect: Decrease the Range of the Linear Program.- 10.3.3. Find_Test: Determine the Median.- 10.3.4. Assembling the Algorithm.- 10.4. Linear Programming in Three and Higher Dimensions.- 10.4.1. The Geometry of Pruning.- 10.4.2. The Geometry of Bisecting.- 10.4.3. Searching Lines in the Plane.- 10.4.4. The Geometry of Searching.- 10.4.5. The Overall Algorithm.- 10.5. Exercises and Research Problems.- 10.6. Bibliographic Notes.- 11 Planar Point Location Search.- 11.1. Euler's Relation for Planar Graphs.- 11.2. The Geometry of Monotone Subdivisions.- 11.3. A Tree of Separators for Point Location.- 11.4. Representing a Plane Subdivision.- 11.5. Constructing a Family of Separators.- 11.6. Optimal Search by Connecting Separators.- 11.7. Constructing the Layered DAG.- 11.8. Refining Non-Monotone Subdivisions.- 11.9. Exercises and Research Problems.- 11.10. Bibliographic Notes.- III Geometric and Algorithmic Applications.- 12 Problems for Configurations and Arrangements.- 12.1. Largest Convex Subsets.- 12.2. The Visibility Graph for Line Segments.- 12.3. Degeneracies in Configurations.- 12.4. Minimum Measure Simplices.- 12.5. Computing Ranks: Sorting in d Dimensions?.- 12.6. A Vector-Sum Maximization Problem.- 12.7. Exercises and Research Problems.- 12.8. Bibliographic Notes.- 13 Voronoi Diagrams.- 13.1. Classical Voronoi Diagrams.- 13.2. Applications in the Plane.- 13.2.1. The Post Office Problem.- 13.2.2. Triangulating Point Sets.- 13.2.3. Delaunay Triangulations from Convex Hulls.- 13.2.4. Finding Closest Neighbors.- 13.2.5. Minimum Spanning Trees.- 13.2.6. Shapes of Point Sets.- 13.3. Higher-Order Voronoi Diagrams.- 13.4. The Complexity of Higher-Order Voronoi Diagrams.- 13.5. Constructing Higher-Order Voronoi Diagrams.- 13.6. Power Diagrams.- 13.7. Exercises and Research Problems.- 13.8. Bibliographic Notes.- 14 Separation and Intersection in the Plane.- 14.1. Constructing Ham-Sandwich Cuts in Two Dimensions.- 14.1.1. Ham-Sandwich Cuts and Duality.- 14.1.2. Testing a Line.- 14.1.3. Finding Test Lines and Pruning.- 14.1.4. The Overall Algorithm.- 14.2. Answering Line Queries.- 14.2.1. The Ham-Sandwich Tree.- 14.2.2. Point Location in Arrangements.- 14.3. A Self-Dual Intersection Problem.- 14.4. Triangular Range Queries.- 14.5. Exercises and Research Problems.- 14.6. Bibliographic Notes.- 15 Paradigmatic Design of Algorithms.- 15.1. The Problem: Stabbing Line Segments in the Plane.- 15.2. Geometric Transformation.- 15.3. Combinatorial Analysis.- 15.4. Divide-and-Conquer.- 15.5. Incremental Construction.- 15.6. Prune-and-Search.- 15.7. The Locus Approach.- 15.8. Dynamization by Decomposition.- 15.9. Exercises and Research Problems.- 15.10. Bibliographic Notes.- References.- Appendix A Definitions.- Appendix B Notational Conventions.

موضوع مستند نشده

Algorytmy.

موضوع مستند نشده

Geometria kombinatoryczna.

شماره رده

نشانه اثر

مستند نام اشخاص تاييد نشده

Herbert Edelsbrunner.

مستند نام اشخاص تاييد نشده

Herbert Edelsbrunner

مستند نام اشخاص تاييد نشده

Springer-Verlag (Berlin)

نام الکترونيکي

نوع ماده

[Book]

تكميل شده

Y