عنوان

Algorithms in combinatorial geometry

(Number (ISBN

3642615686

(Number (ISBN

3642648738

(Number (ISBN

9783642615689

(Number (ISBN

9783642648731

Number

b571822

Title Proper

Algorithms in combinatorial geometry

General Material Designation

[Book]

First Statement of Responsibility

Herbert Edelsbrunner.

Place of Publication, Distribution, etc.

Berlin

Name of Publisher, Distributor, etc.

Springer-Verlag, [post

Date of Publication, Distribution, etc.

2005], cop. 1987.

Specific Material Designation and Extent of Item

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

Series Title

EATCS Monographs on Theoretical Computer Science, vol. 10.

Text of Note

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

Text of Note

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.

Class number

Book number

Herbert Edelsbrunner.

Herbert Edelsbrunner

Springer-Verlag (Berlin)

Electronic name

[Book]

Y