Lectures on Discrete Geometry by Jiří Matoušek (auth.), Jiří Matoušek (eds.)

By Jiří Matoušek (auth.), Jiří Matoušek (eds.)

Discrete geometry investigates combinatorial homes of configurations of geometric items. To a operating mathematician or computing device scientist, it deals subtle effects and methods of serious variety and it's a origin for fields reminiscent of computational geometry or combinatorial optimization.

This e-book is basically a textbook creation to varied parts of discrete geometry. In every one zone, it explains a number of key effects and strategies, in an obtainable and urban demeanour. It additionally includes extra complex fabric in separate sections and therefore it could possibly function a set of surveys in numerous narrower subfields. the most issues comprise: fundamentals on convex units, convex polytopes, and hyperplane preparations; combinatorial complexity of geometric configurations; intersection styles and transversals of convex units; geometric Ramsey-type effects; polyhedral combinatorics and high-dimensional convexity; and finally, embeddings of finite metric areas into normed spaces.

Jiri Matousek is Professor of desktop technology at Charles collage in Prague. His study has contributed to numerous of the thought of components and to their algorithmic functions. this can be his 3rd book.

Show description

Read or Download Lectures on Discrete Geometry PDF

Best geometry books

Geometry of Complex Numbers (Dover Books on Mathematics)

Illuminating, commonly praised ebook on analytic geometry of circles, the Moebius transformation, and 2-dimensional non-Euclidean geometries. "This publication will be in each library, and each professional in classical functionality idea may be acquainted with this fabric. the writer has played a unique carrier via making this fabric so very easily available in one ebook.

Geometric Tomography (Encyclopedia of Mathematics and its Applications)

Geometric tomography bargains with the retrieval of knowledge a few geometric item from facts relating its projections (shadows) on planes or cross-sections by means of planes. it's a geometric relative of automated tomography, which reconstructs a picture from X-rays of a human sufferer. the topic overlaps with convex geometry and employs many instruments from that region, together with a few formulation from quintessential geometry.

First Steps in Differential Geometry: Riemannian, Contact, Symplectic (Undergraduate Texts in Mathematics)

Differential geometry arguably deals the smoothest transition from the traditional college arithmetic series of the 1st 4 semesters in calculus, linear algebra, and differential equations to the better degrees of abstraction and evidence encountered on the higher department via arithmetic majors. at the present time it really is attainable to explain differential geometry as "the research of constructions at the tangent space," and this article develops this perspective.

Additional info for Lectures on Discrete Geometry

Sample text

If a convex body K is not required to be sym­ metric about 0, then it can have arbitrarily large volume without con­ taining a lattice point. But any lattice-point free body has to be fiat: For every dimension d there exists c( d) such that any convex body K c Rd with K n z d 0 has lattice width at Inost c(d) . The lattice width of K is defined as min{maxx E K (x, y) - minx E K (x, y): y E z d \ { 0}}; geometrically, we essentially count the number of hyper­ planes orthogonal to y, spanned by points of zd , and intersecting K.

Many of the geometric Ramsey-type theorems, including the Erdos­ Szekeres theorem, can be derived from Ramsey's theorem. But the quantita­ tive bound for the N in Ramsey's theorem is very large, and consequently, 30 Chapter 3: Convex Independent Subsets the size of the "regular" configurations guaranteed by proofs via Ramsey's theorem is very small. Other proofs tailored to the particular problems and using more of their geometric structure often yield much better quantitative results. 3 . 1 The Erdos-Szekeres Theorem 3 .

Y large planar point set in general position contains a 5-hole. Proof. By the Erdos-Szekeres theorem, we may assume that there exists a 6-point convex independent subset of our set X. Consider a 6-point convex independent subset H C X with the smallest possible IX n conv(H) I . Let I == conv(H) n (X \ H) be the points inside the convex hull of H. • • • If I == 0, we have a 6-hole. If there is one point x in I, we consider a diagonal that partitions the hexagon into two quadrilaterals: The point x lies in one of these quadrilaterals, and the vertices of the other quadrilateral together with x form a 5-hole.

Download PDF sample

Rated 4.18 of 5 – based on 35 votes