Skip to main content
main-content

Über dieses Buch

Discrete and computational geometry are two fields which in recent years have benefitted from the interaction between mathematics and computer science. The results are applicable in areas such as motion planning, robotics, scene analysis, and computer aided design. The book consists of twelve chapters summarizing the most recent results and methods in discrete and computational geometry. All authors are well-known experts in these fields. They give concise and self-contained surveys of the most efficient combinatorical, probabilistic and topological methods that can be used to design effective geometric algorithms for the applications mentioned above. Most of the methods and results discussed in the book have not appeared in any previously published monograph. In particular, this book contains the first systematic treatment of epsilon-nets, geometric tranversal theory, partitions of Euclidean spaces and a general method for the analysis of randomized geometric algorithms. Apart from mathematicians working in discrete and computational geometry this book will also be of great use to computer scientists and engineers, who would like to learn about the most recent results.

Inhaltsverzeichnis

Frontmatter

Introduction

Abstract
Had you asked a layman in the fifties what mathematics was about, he would have thought “of dull uninspiring numbers, of a lifeless mechanism which functions according to laws of inescapable necessity” [1]. Coming from a family of many mathematicians, I learned in my younger days how to refute the widely held opinion that mathematicians are mainly concerned with counting, calculating and computing. Euclid’s famous proof of the existence of infinitely many primes by reductio ad absurdum was the standard example of a “philosophical” argument using no calculation: Assume, for the sake of contradiction, that there were only finitely many primes p 1, p 2,…, p n . Then p 1 p 2p n + 1 could not have any prime divisor, which is clearly impossible! I was trained to believe that mathematics, a “gigantic, bold venture of the mind”, was “die Schule des Denkens” (the school of thinking) [2, 3]. For me it had much more to do with infinity, philosophy and puzzles, than with counting or tedious computation.
János Pach

Chapter I. Combinatorics and Algorithms of Arrangements

Abstract
In this chapter we study the combinatorial structure of arrangements of algebraic curves or surfaces in low-dimensional Euclidean space. Such arrangements arise in many geometric problems, as will be exemplified below. To introduce the class of problems we will be interested in, we begin with the following concrete example, taken from the theory of motion planning in robotics.
Leonidas Guibas, Micha Sharir

Chapter II. Backwards Analysis of Randomized Geometric Algorithms

Abstract
The theme of this chapter is a rather simple method that has proved very potent in the analysis of the expected performance of various randomized algorithms and data structures in computational geometry. The method can be described as “analyze a randomized algorithm as if it were running backwards in time, from output to input.” We apply this type of analysis to a variety of algorithms, old and new, and obtain solutions with optimal or near optimal expected performance for a plethora of problems in computational geometry, such as computing Delaunay triangulations of convex polygons, computing convex hulls of point sets in the plane or in higher dimensions, sorting, intersecting line segments, linear programming with a fixed number of variables, and others.
Raimund Seidel

Chapter III. Epsilon-Nets and Computational Geometry

Abstract
In this chapter, we present some results from the theory of range spaces of finite VC-dimension. We introduce canonical geometric range spaces and we indicate how other range spaces encountered in computational geometry can be embedded into the canonical ones. As applications of ε-nets for computational geometry problems, we mention the Cutting lemma, the Short edge lemma and the construction of an arrangement with small zones. We then indicate some improvements of these results when the application of general ε-net results is replaced by other methods, and we also address the issue of de-randomizing the algorithms based on ε-nets and related probabilistic techniques. We give main ideas of several proofs.
Jiří Matoušek

Chapter IV. Complexity of Polytope Volume Computation

Abstract
We survey some recent results on the complexity of computing the vol­ume of convex n-dimensional polytopes.
Leonid Khachiyan

Chapter V. Allowable Sequences and Order Types in Discrete and Computational Geometry

Abstract
The allowable sequence associated to a configuration of points was first developed by the authors in order to investigate what combinatorial structure lay behind the Erdős-Szekeres conjecture (that any 2 n-2 + 1 points in general position in the plane contain among them n points which are in convex position). Though allowable sequences did not lead to any progress on this ancient problem, there did emerge an object that had considerable intrinsic interest, that turned out to be related to some other well-studied structures such as pseudoline arrangements and oriented matroids, and that had as well a combinatorial simplicity and suggestiveness which turned out to be effective in the solution of several other classical problems. These connections and applications are discussed in Sections 2, 3, and 4 of this paper.
Jacob E. Goodman, Richard Pollack

Chapter VI. Hyperplane Approximation and Related Topics

Abstract
This chapter is a survey on problems related to the approximation of finite weighted point sets in d-space by hyperplanes with respect to certain metrics. From the viewpoint of Computational Geometry, we shall discuss the orthogonal and vertical L 1-fit problem as well as the orthogonal and vertical L -fit problem. Though we shall lay emphasis on the othogonal L 1-fit problem, suitable generalizations to the other problems are given as well. For example, the reader will find informations on k- flats, k ∈ {0,…, d - 2}, being extremal with respect to finite point sets and leading also to the well-known Fermat-Torricelli point and related subjects.
Nikolai M. Korneenko, Horst Martini

Chapter VII. Geometric Transversal Theory

Abstract
Geometric transversal theory has its origins in Helly’s theorem: Theorem 1.1 (Helly’s Theorem) [49]. Suppose A is a family of at least d + 1 convex sets in IR d , and A is finite or each member of A is compact. Then if every d + 1 members of A have a common point, there is a point common to all the members of A.
Jacob E. Goodman, Richard Pollack, Rephael Wenger

Chapter VIII. Hadwiger-Levi’s Covering Problem Revisited

Abstract
A well-known problem of discrete geometry is due to Hadwiger (1957), (1960) and Levi (1955). The following conjecture concerning this problem was published by Hadwiger (1957), (1960) and also by Gohberg and Markus (1960): Any convex body of E d , d ≥ 1 (i.e. any compact convex subset of the d-dimensional Euclidean space E d with non-empty interior) can be covered by 2 d smaller homothetic bodies and equality is attained only for d-dimensional parallelotopes. This conjecture has stimulated a lot of research in geometry. To survey the basic results we need some simple definitions.
Károly Bezdek

Chapter IX. Geometric and Combinatorial Applications of Borsuk’s Theorem

Abstract
In this chapter geometric and combinatorial applications and extensions of the Borsuk theorem [Bo] are presented. This theorem has several equivalent forms. Let S d denote the d-dimensional sphere, i.e., the boundary of the Euclidean unit ball in R d+1.
Imre Bárány

Chapter X. A Survey of Recent Results in the Theory of Packing and Covering

Abstract
The theory of packing and covering, originated as an offspring of number theory and crystallography early in this century, has quickly gained interest of its own and is now an essential part of discrete geometry. The theory owes its early development to its aesthetic appeal and its classical flavor, but more recently, some of its topics have been found related to the rapidly developing areas of mathematics connected with computer science, and the theory of packing and covering has been boosted by a renewed interest.
Gábor Fejes Tóth, Wlodzimierz Kuperberg

Chapter XI. Recent Developments in Combinatorial Geometry

Abstract
Over a span of fifty years Paul Erdős has written many articles with this or a similar title. His countless results, which were obtained by the application of combinatorial and counting (random) methods, and the many deep problems raised and popularized in these papers, generated much research in combinatorics and graph theory. They played an important role in the emergence of a number of new areas in mathematics. One of these is combinatorial geometry, the study of extremal problems about finite arrangements of points, lines, circles, etc.
W. Moser, J. Pach

Chapter XII. Set Theoretic Constructions in Euclidean Spaces

Abstract
The most important methods of constructing, via the axiom of choice, various sets and decompositions in Euclidean spaces, omitting some geometrical configurations are surveyed.
Péter Komjáth

Backmatter

Weitere Informationen