Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

1993 | Book

Introduction Read chapter Read first chapter

New Trends in Discrete and Computational Geometry

Editor: János Pach

Publisher: Springer Berlin Heidelberg

Book Series : Algorithms and Combinatorics

Included in: Professional Book Archive

Login to get access
insite
SEARCH

About this book

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.

Table of Contents

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 2 …p 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
Metadata
Title
New Trends in Discrete and Computational Geometry
Editor
János Pach
Copyright Year
1993
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-58043-7
Print ISBN
978-3-540-55713-5
DOI
https://doi.org/10.1007/978-3-642-58043-7