Lectures on Discrete Geometry de Ji& Matousek

Lectures on Discrete Geometry

Ji& Matousek

Evoluția geometriei discrete în ultimele decenii a transformat acest domeniu dintr-o ramură teoretică a matematicii într-un fundament indispensabil pentru geometria computațională și optimizarea combinatorie. Notăm cu interes modul în care lucrarea Lectures on Discrete Geometry, semnată de Ji& Matousek, reușește să sintetizeze această tranziție, oferind un cadru riguros pentru studiul proprietăților combinatorii ale configurațiilor geometrice. Ediția din 2002 de la Springer se distinge printr-o abordare pedagogică rar întâlnită la nivel de studii masterale, făcând accesibile rezultate sofisticate fără a sacrifica profunzimea matematică. Subliniem organizarea logică a conținutului, care ghidează cititorul de la fundamentele convexității și Teorema lui Minkowski către subiecte avansate precum complexitatea combinatorie a configurațiilor geometrice și scufundările spațiilor metrice finite în spații normate. Față de alte lucrări ale autorului, precum Geometry, Structure and Randomness in Combinatorics, care se concentrează pe tendințe curente și articole de cercetare în teoria grafurilor și Ramsey, volumul de față servește drept bază solidă, un manual de referință ce pune accent pe metode și demonstrații clare. Putem afirma că acest titlu completează perspectiva oferită de Combinatorial and Computational Geometry de Jacob E. Goodman. În timp ce volumul lui Goodman este o colecție de lucrări de cercetare și studii ce explorează sinergia dintre discipline, lucrarea lui Matoušek oferă o structură de curs coerentă, axată pe construcția progresivă a competențelor necesare unui matematician sau informatician. Stilul este concret, evitând abstractizarea excesivă, dar incluzând secțiuni separate pentru material avansat, ceea ce o face utilă și ca resursă de referință pentru experți.

Citește tot Restrânge

De ce să citești această carte

Recomandăm această carte studenților și cercetătorilor care doresc o introducere sistematică în geometria discretă. Veți câștiga o înțelegere profundă a metodelor combinatorii aplicate în geometrie, esențiale pentru algoritmi și optimizare. Este un instrument de lucru clar, scris de unul dintre cei mai respectați pedagogi ai domeniului, oferind un echilibru perfect între teoria convexității și aplicațiile sale practice în informatică.

Cuprins

1 Convexity.- 1.1 Linear and Affine Subspaces, General Position.- 1.2 Convex Sets, Convex Combinations, Separation.- 1.3 Radon’s Lemma and Helly’s Theorem.- 1.4 Centerpoint and Harn Sandwich.- 2 Lattices and Minkowski’s Theorem.- 2.1 Minkowski’s Theorem.- 2.2 General Lattices.- 2.3 An Application in Number Theory.- 3 Convex Independent Subsets.- 3.1 The Erd?s-Szekeres Theorem.- 3.2 Horton Sets.- 4 Incidence Problems.- 4.1 Formulation.- 4.2 Lower Bounds: Incidences and Unit Distances.- 4.3 Point-Line Incidences via Crossing Numbers.- 4.4 Distinct Distances via Crossing Numbers.- 4.5 Point-Line Incidences via Cuttings.- 4.6 A Weaker Cutting Lemma.- 4.7 The Cutting Lemma: A Tight Bound.- 5 Convex Polytopes.- 5.1 Geometric Duality.- 5.2 H-Polytopes and V-Polytopes.- 5.3 Faces of a Convex Polytope.- 5.4 Many Faces: The Cyclic Polytopes.- 5.5 The Upper Bound Theorem.- 5.6 The Gale Transform.- 5.7 Voronoi Diagrams.- 6 Number of Faces in Arrangements.- 6.1 Arrangements of Hyperplanes.- 6.2 Arrangements of Other Geometric Objects.- 6.3 Number of Vertices of Level at Most k.- 6.4 The Zone Theorem.- 6.5 The Cutting Lemma Revisited.- 7 Lower Envelopes.- 7.1 Segments and Davenport-Schinzel Sequences.- 7.2 Segments: Superlinear Complexity of the Lower Envelope.- 7.3 More on Davenport-Schinzel Sequences.- 7.4 Towards the Tight Upper Bound for Segments.- 7.5 Up to Higher Dimension: Triangles in Space.- 7.6 Curves in the Plane.- 7.7 Algebraic Surface Patches.- 8 Intersection Patterns of Convex Sets.- 8.1 The Fractional Helly Theorem.- 8.2 The Colorful Carathéodory Theorem.- 8.3 Tverberg’s Theorem.- 9 Geometric Selection Theorems.- 9.1 A Point in Many Simplices: The First Selection Lemma.- 9.2 The Second Selection Lemma.- 9.3 Order Types and the Same-Type Lemma.- 9.4 A Hypergraph Regularity Lemma.- 9.5 A Positive-Fraction Selection Lemma.- 10 Transversals and Epsilon Nets.- 10.1 General Preliminaries: Transversals and Matchings.- 10.2 Epsilon Nets and VC-Dimension.- 10.3 Bounding theVC-Dimension and Applications.- 10.4 Weak Epsilon Nets for Convex Sets.- 10.5 The Hadwiger-Debrunner (p, q)-Problem.- 10.6 A (p, q)-Theorem for Hyperplane Transversals.- 11 Attempts to Count k-Sets.- 11.1 Definitions and First Estimates.- 11.2 Sets with Many Halving Edges.- 11.3 The Lovász Lemma and Upper Bounds in All Dimensions.- 11.4 A Better Upper Bound in the Plane.- 12 Two Applications of High-Dimensional Polytopes.- 12.1 The Weak Perfect Graph Conjecture.- 12.2 The Brunn-Minkowski Inequality.- 12.3 Sorting Partially Ordered Sets.- 13 Volumes in High Dimension.- 13.1 Volumes, Paradoxes of High Dimension, and Nets.- 13.2 Hardness of Volume Approximation.- 13.3 Constructing Polytopes of Large Volume.- 13.4 Approximating Convex Bodies by Ellipsoids.- 14 Measure Concentration and Almost Spherical Sections.- 14.1 Measure Concentration on the Sphere.- 14.2 Isoperimetric Inequalities and More on Concentration.- 14.3 Concentration of Lipschitz Functions.- 14.4 Almost Spherical Sections:The First Steps.- 14.5 Many Faces of Symmetric Polytopes.- 14.6 Dvoretzky’s Theorem.- 15 Embedding Finite Metric Spaces into Normed Spaces.- 15.1 Introduction: Approximate Embeddings.- 15.2 The Johnson-Lindenstrauss Flattening Lemma.- 15.3 Lower Bounds By Counting.- 15.4 A Lower Bound for the Hamming Cube.- 15.5 A Tight Lower Bound via Expanders.- 15.6 Upper Bounds for ??-Embeddings.- 15.7 Upper Bounds for Euclidean Embeddings.- What Was It About? An Informal Summary.- Hints to Selected Exercises.

Recenzii

From the reviews:
"Discrete geometry is not quite a newcomer on the stage of mathematics. … The book under review covers … a gap in the pedagogical literature, providing an expository treatment of a wide range of topics in discrete geometry, without assuming too many prerequisites from the reader. … it will be ideal to be used both as a textbook and for self-study. … In fact … this book can be used as a ‘mathematical companion’ to a textbook on computational geometry … ." (Paul A. Blaga, Studia Universitatis Babes-Bolyai Mathematica, Vol. XLVIII (1), March, 2004)
"Matoušek’s excellent new book concerns discrete geometry. … The style is clear and pleasant; things are streamlined and collected in one place, and are explained on simple, concrete examples. … a final chapter on ‘What was it about? An informal summary’ was an innovation that I found to be an excellent idea. Lectures on discrete geometry is a splendid book. I recommend it both to students and researchers in the field, as well as to those who like mathematics for its own inherent beauty." (Imre Bárány, Bulletin of the London Mathematical Society, Issue 35, 2003)
"This book is primarily a textbook introduction to various areas of discrete geometry. In each area, it explains several key results and methods, in an accessible and concrete manner. It also contains more advanced material in separate sections, and thus, it can serve as a collection of surveys in several narrower subfields." (L’ENSEIGNEMENT MATHEMATIQUE, Vol. 48 (3-4), 2002)
"This is an introduction to the field of discrete geometry understood as the investigation of combinatorial properties of configurations of (usually finitely many) geometric objects … . The book is written in a lively and stimulating but very precise style and contains many figures. It gives a good impression of the richness and the relevance of the field." (Johann Linhart, Zentralblatt Math, Vol. 999 (24), 2002)

Textul de pe ultima copertă

Discrete geometry investigates combinatorial properties of configurations of geometric objects. To a working mathematician or computer scientist, it offers sophisticated results and techniques of great diversity and it is a foundation for fields such as computational geometry or combinatorial optimization.

This book is primarily a textbook introduction to various areas of discrete geometry. In each area, it explains several key results and methods, in an accessible and concrete manner. It also contains more advanced material in separate sections and thus it can serve as a collection of surveys in several narrower subfields. The main topics include: basics on convex sets, convex polytopes, and hyperplane arrangements; combinatorial complexity of geometric configurations; intersection patterns and transversals of convex sets; geometric Ramsey-type results; polyhedral combinatorics and high-dimensional convexity; and lastly, embeddings of finite metric spaces into normed spaces.

Jiri Matousek is Professor of Computer Science at Charles University in Prague. His research has contributed to several of the considered areas and to their algorithmic applications. This is his third book.

Lectures on Discrete Geometry

Preț: 635^.51 lei

Carte tipărită la comandă

Specificații

Public țintă

De ce să citești această carte

Cuprins

Recenzii

Textul de pe ultima copertă

Caracteristici

Ficțiune

Business

Medicină

Lifestyle

Copii și adolescenți

Biografii

Artă, arhitectură şi design

Calculatoare și IT

Științe

Tehnologie și inginerie

Papetărie, jocuri, reviste

Lectures on Discrete Geometry

Preț: 635.51 lei

Specificații

V-ar putea interesa

Public țintă

De ce să citești această carte

Cuprins

Recenzii

Textul de pe ultima copertă

Caracteristici

Papetărie, jocuri, reviste

Preț: 635^.51 lei