Ebook Ruler, Compass, and Computer: The Design and Analysis of Geometric Algorithms
Computational geometry is the branch of computer science concerned with the design and analysis of algorithms for geometric problems. Among the tools of computational geometry there seems to be a small set of techniques and structures that have such a wide range of applications that they deserve to be called fundamental, in the same sense that balanced binary trees and sorting are fundamental for combinatorial algorithms in general. In this paper we will discuss and illustrate a number of these fundamental techniques of computational geometry. In most instances we give a worked out example of a problem solved by each of the techniques we discuss.
Historical note. The term "computational geometry" was originally coined by Robin Forrest [23] to denote the study of computational techniques in the realm of computer-aided geometric design. More recently, this term has been used to name a somewhat different field, in a way broader and in a way narrower than Forrest's conception, a field which is now considered part of theoretical computer science. This new use of the name "computational geometry," whose origin can be traced to Shamos [65], refers to the design and analysis of algorithms for all kinds of geometric problems, not necessarily in computer aided design. This is the sense in which the term will be used in this paper.
Influenced by other branches of theoretical computer science, this new field has focused on the design of efficient algorithms when the number of objects in the input is large. This consideration has led to the development of asymptotically efficient (and sometimes practical) algorithms for problems dealing with large numbers of simple underlying objects in two or three dimensions: points, lines, planes, polygons, and polyhedra. This situation is to be contrasted with that of computer-aided design, where the underlying objects are more complex, say bicubic surface patches, but where asymptotic considerations tend to be less dominant. Abstracting away from this dichotomy, we can say that the goal of computational geometry is to collect and study all techniques relevant to the computer description and manipulation of geometric objects, within the wider framework of the analysis of algorithms.
It has been known since the time of Descartes that any geometrical problem can be recast in purely algebraic terms. It may therefore seem unnecessary to have a special discipline for geometric problems, distinct from numerical algebra and analysis. Indeed, some problems in geometry are best solved by algebraic methods, like computing the area of a polygon; but it is equally true that most geometrical concepts and algorithms are best "seen" and studied in their own framework. Furthermore, most problems in computational geometry are neither purely combinatorial, nor purely numerical, but rather an intimate mixture of both. Computational geometry has therefore its unique flavor, and its unique combination of tools and techniques.
Many fundamental problems and results of computational geometry had been studied well before the field was recognized as a discipline in itself. Actually, we can say that computational geometry is the most ancient branch of computer science: the constructions of Euclidean geometry are legitimate algorithms, based on a well-defined, finite set of elementary operations.
In fact, Euclidean geometry is where several of the key concepts of computer science were first introduced: the close relationship between an algorithm and the proof of its correctness, the first examples of "provably unsolvable" problems (doubling the cube, trisecting the angle, squaring the circle), and so forth. Early this century the French mathematician Lemoine introduced (without much success) the idea of "computational complexity" of a geometrical construction, by counting the number of elementary steps it required. Other 19th century geometers, like Mohr and Mascheroni, showed that the ruler and compass of classical geometry could be replaced by other sets of tools (compass alone, ruler and scale, ruler and fixed-aperture compass, and so on). Their work is a close parallel to the theorems establishing equivalence of power for different flavors of Turing machines by simulation.
Because of the long pre-history of the field and its large number of applications, the fundamental results and techniques of computational geometry are widely scattered in publications that range from highly abstract mathematics texts to applications oriented journals. It is only very recently that we are starting to see journals devoted explicitly (at least in part) to computational geometry, such as Discrete and Computational Geometry and Algorithmica.
Contents
1 Introduction
Part A: Algorithm Design Techniques
Al The locus approach
A2 Geometric transformations
A3 Duality
A4 Space sweep techniques
A5 The configuration space approach
A6 Separator techniques
A7 Decimation
A8 Hierarchical structures
Part B: Data Structures
Bl Fractional cascading
B2 Finger trees
B3 Persistent data structures
Part C: Analysis Techniques
CI Exploiting results from combinatorial geometry
C2 Davenport-Schinzel sequences
C3 Amortized analysis
C4 Average-case analysis
Epilogue
Acknowledgements
References
Download
PDF Ebook Ruler, Compass, and Computer: The Design and Analysis of Geometric Algorithms
Posted in :
