Muutke küpsiste eelistusi

E-raamat: Geometric Approximation Algorithms

Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 136,58 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Geometric Approximation AlgorithmsSuurem pilt
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

Exact algorithms for dealing with geometric objects are complicated, hard to implement in practice, and slow. Over the last 20 years a theory of geometric approximation algorithms has emerged. These algorithms tend to be simple, fast, and more robust than their exact counterparts. This book is the first to cover geometric approximation algorithms in detail. In addition, more traditional computational geometry techniques that are widely used in developing such algorithms, like sampling, linear programming, etc., are also surveyed. Other topics covered include approximate nearest-neighbor search, shape approximation, coresets, dimension reduction, and embeddings. The topics covered are relatively independent and are supplemented by exercises. Close to 200 color figures are included in the text to illustrate proofs and ideas.
Preface xi
Chapter 1 The Power of Grids-Closest Pair and Smallest Enclosing Disk 1(12)
1.1 Preliminaries
1(1)
1.2 Closest pair
1(4)
1.3 A slow 2-approximation algorithm for the k-enclosing disk
5(1)
1.4 A linear time 2-approximation for the k-enclosing disk
6(4)
1.5 Bibliographical notes
10(1)
1.6 Exercises
11(2)
Chapter 2 Quadtrees–Hierarchical Grids 13(16)
2.1 Quadtrees–a simple point-location data-structure
13(2)
2.2 Compressed quadtrees
15(5)
2.3 Dynamic quadtrees
20(4)
2.4 Bibliographical notes
24(2)
2.5 Exercises
26(3)
Chapter 3 Well-Separated Pair Decomposition 29(18)
3.1 Well-separated pair decomposition (WSPD)
29(4)
3.2 Applications of WSPD
33(7)
3.3 Semi-separated pair decomposition (SSPD)
40(3)
3.4 Bibliographical notes
43(1)
3.5 Exercises
44(3)
Chapter 4 Clustering-Definitions and Basic Algorithms 47(14)
4.1 Preliminaries
47(2)
4.2 On k-center clustering
49(2)
4.3 On k-median clustering
51(6)
4.4 On k-means clustering
57(1)
4.5 Bibliographical notes
57(2)
4.6 Exercises
59(2)
Chapter 5 On Complexity, Sampling, and s-Nets and s-Samples 61(26)
5.1 VC dimension
61(3)
5.2 Shattering dimension and the dual shattering dimension
64(6)
5.3 On s-nets and e-sampling
70(5)
5.4 Discrepancy
75(5)
5.5 Proof of the e-net theorem
80(2)
5.6 A better bound on the growth function
82(1)
5.7 Bibliographical notes
83(1)
5.8 Exercises
84(3)
Chapter 6 Approximation via Reweighting 87(16)
6.1 Preliminaries
87(1)
6.2 Computing a spanning tree with low crossing number
88(6)
6.3 Geometric set cover
94(4)
6.4 Geometric set cover via linear programming
98(2)
6.5 Bibliographical notes
100(1)
6.6 Exercises
100(3)
Chapter 7 Yet Even More on Sampling 103(18)
7.1 Introduction
103(3)
7.2 Applications
106(3)
7.3 Proof of Theorem 7.7
109(10)
7.4 Bibliographical notes
119(1)
7.5 Exercises
119(2)
Chapter 8 Sampling and the Moments Technique 121(14)
8.1 Vertical decomposition
121(4)
8.2 General settings
125(3)
8.3 Applications
128(2)
8.4 Bounds on the probability of a region to be created
130(1)
8.5 Bibliographical notes
131(2)
8.6 Exercises
133(2)
Chapter 9 Depth Estimation via Sampling 135(10)
9.1 The at most k-levels
135(1)
9.2 The crossing lemma
136(4)
9.3 A general bound for the at most k-weight
140(2)
9.4 Bibliographical notes
142(1)
9.5 Exercises
143(2)
Chapter 10 Approximating the Depth via Sampling and Emptiness 145(6)
10.1 From emptiness to approximate range counting
145(3)
10.2 Application: Halfplane and halfspace range counting
148(1)
10.3 Relative approximation via sampling
149(1)
10.4 Bibliographical notes
150(1)
10.5 Exercises
150(1)
Chapter 11 Random Partition via Shifting 151(12)
11.1 Partition via shifting
151(4)
11.2 Hierarchical representation of a point set
155(3)
11.3 Low quality ANN search
158(2)
11.4 Bibliographical notes
160(1)
11.5 Exercises
160(3)
Chapter 12 Good Triangulations and Meshing 163(14)
12.1 Introduction-good triangulations
163(1)
12.2 Triangulations and fat triangulations
164(4)
12.3 Analysis
168(7)
12.4 The result
175(1)
12.5 Bibliographical notes
176(1)
Chapter 13 Approximating the Euclidean Traveling Salesman Problem (TSP) 177(14)
13.1 The TSP problem-introduction
177(1)
13.2 When the optimal solution is friendly
178(4)
13.3 TSP approximation via portals and sliding quadtrees
182(8)
13.4 Bibliographical notes
190(1)
13.5 Exercises
190(1)
Chapter 14 Approximating the Euclidean TSP Using Bridges 191(12)
14.1 Overview
191(1)
14.2 Cuts and bridges
192(6)
14.3 The dynamic programming
198(4)
14.4 The result
202(1)
14.5 Bibliographical notes
202(1)
Chapter 15 Linear Programming in Low Dimensions 203(14)
15.1 Linear programming
203(2)
15.2 Low-dimensional linear programming
205(3)
15.3 Linear programming with violations
208(1)
15.4 Approximate linear programming with violations
209(1)
15.5 LP-type problems
210(3)
15.6 Bibliographical notes
213(2)
15.7 Exercises
215(2)
Chapter 16 Polyhedrons, Polytopes, and Linear Programming 217(16)
16.1 Preliminaries
217(2)
16.2 Properties of polyhedrons
219(8)
16.3 Vertices of a polytope
227(3)
16.4 Linear programming correctness
230(2)
16.5 Bibliographical notes
232(1)
16.6 Exercises
232(1)
Chapter 17 Approximate Nearest Neighbor Search in Low Dimension 233(10)
17.1 Introduction
233(1)
17.2 The bounded spread case
233(3)
17.3 ANN-the unbounded general case
236(2)
17.4 Low quality ANN search via the ring separator tree
238(2)
17.5 Bibliographical notes
240(2)
17.6 Exercises
242(1)
Chapter 18 Approximate Nearest Neighbor via Point-Location 243(14)
18.1 ANN using point-location among balls
243(7)
18.2 ANN using point-location among approximate balls
250(2)
18.3 ANN using point-location among balls in low dimensions
252(1)
18.4 Approximate Voronoi diagrams
253(2)
18.5 Bibliographical notes
255(1)
18.6 Exercises
256(1)
Chapter 19 Dimension Reduction-The Johnson-Lindenstrauss (JL) Lemma 257(12)
19.1 The Brunn-Minkowski inequality
257(3)
19.2 Measure concentration on the sphere
260(3)
19.3 Concentration of Lipschitz functions
263(1)
19.4 The Johnson-Lindenstrauss lemma
263(3)
19.5 Bibliographical notes
266(1)
19.6 Exercises
267(2)
Chapter 20 Approximate Nearest Neighbor (ANN) Search in High Dimensions 269(10)
20.1 ANN on the hypercube
269(5)
20.2 LSH and ANN in Euclidean space
274(2)
20.3 Bibliographical notes
276(3)
Chapter 21 Approximating a Convex Body by an Ellipsoid 279(4)
21.1 Ellipsoids
279(3)
21.2 Bibliographical notes
282(1)
Chapter 22 Approximating the Minimum Volume Bounding Box of a Point Set 283(8)
22.1 Some geometry
283(1)
22.2 Approximating the minimum volume bounding box
284(2)
22.3 Exact algorithm for the minimum volume bounding box
286(2)
22.4 Approximating the minimum volume bounding box in three dimensions
288(1)
22.5 Bibliographical notes
289(1)
22.6 Exercises
289(2)
Chapter 23 Coresets 291(16)
23.1 Coreset for directional width
291(6)
23.2 Approximating the extent of lines and other creatures
297(4)
23.3 Extent of polynomials
301(1)
23.4 Roots of polynomials
302(4)
23.5 Bibliographical notes
306(1)
23.6 Exercises
306(1)
Chapter 24 Approximation Using Shell Sets 307(8)
24.1 Covering problems, expansion, and shell sets
307(3)
24.2 Covering by cylinders
310(3)
24.3 Bibliographical notes
313(1)
24.4 Exercises
313(2)
Chapter 25 Duality 315(8)
25.1 Duality of lines and points
315(3)
25.2 Higher dimensions
318(1)
25.3 Bibliographical notes
319(2)
25.4 Exercises
321(2)
Chapter 26 Finite Metric Spaces and Partitions 323(12)
26.1 Finite metric spaces
323(2)
26.2 Random Partitions
325(2)
26.3 Probabilistic embedding into trees
327(2)
26.4 Embedding any metric space into Euclidean space
329(3)
26.5 Bibliographical notes
332(1)
26.6 Exercises
333(2)
Chapter 27 Some Probability and Tail Inequalities 335(12)
27.1 Some probability background
335(3)
27.2 Tail inequalities
338(4)
27.3 Hoeffding's inequality
342(2)
27.4 Bibliographical notes
344(1)
27.5 Exercises
344(3)
Chapter 28 Miscellaneous Prerequisite 347(2)
28.1 Geometry and linear algebra
347(1)
28.2 Calculus
348(1)
Bibliography 349(8)
Index 357
Sariel Har-Peled, University of Illinois at Urbana-Champaign, IL
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97814704140092e.html
Märksõnad: