Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1985 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Computational Geometry

An Introduction

verfasst von: Franco P. Preparata, Michael Ian Shamos

Verlag: Springer New York

Buchreihe : Monographs in Computer Science

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

From the reviews: "This book offers a coherent treatment, at the graduate textbook level, of the field that has come to be known in the last decade or so as computational geometry. ... ... The book is well organized and lucidly written; a timely contribution by two founders of the field. It clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics. It also points the way to the solution of the more challenging problems in dimensions higher than two." #Mathematical Reviews#1 "... This remarkable book is a comprehensive and systematic study on research results obtained especially in the last ten years. The very clear presentation concentrates on basic ideas, fundamental combinatorial structures, and crucial algorithmic techniques. The plenty of results is clever organized following these guidelines and within the framework of some detailed case studies. A large number of figures and examples also aid the understanding of the material. Therefore, it can be highly recommended as an early graduate text but it should prove also to be essential to researchers and professionals in applied fields of computer-aided design, computer graphics, and robotics." #Biometrical Journal#2

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
Egyptian and Greek geometry were masterpieces of applied mathematics. The original motivation for geometric problems was the need to tax lands accurately and fairly and to erect buildings. As often happens, the mathematics that developed had permanence and significance that far transcend the Pharaoh’s original revenue problem, for Geometry is at the heart of mathematical thinking. It is a field in which intuition abounds and new discoveries are within the compass (so to speak) of nonspecialists.
Franco P. Preparata, Michael Ian Shamos
Chapter 2. Geometric Searching
Abstract
To describe searching in its simplest abstract setting, suppose we have some accumulated data (called the “file”) and some new data item (called the “sample”). Searching consists of relating the sample to the file. Accessory operations—conceptually not a part of searching—may involve absorbing the sample into the file, deleting the sample from the file if already present, and so on. As Knuth (1973) points out, searching means to locate the appropriate record (or records) in a given collection of records.
Franco P. Preparata, Michael Ian Shamos
Chapter 3. Convex Hulls: Basic Algorithms
Abstract
The problem of computing a convex hull is not only central to practical applications, but is also a vehicle for the solution of a number of apparently unrelated questions arising in computational geometry. The computation of the convex hull of a finite set of points, particularly in the plane, has been studied extensively and has applications, for example, in pattern recognition [Akl–CToussaint (1978); Duda–CHart (1973)], image processing [Rosenfeld (1969)] and stock cutting and allocation [Freeman (1974);Sklansky (1972); Freeman–CShapira (1975)].
Franco P. Preparata, Michael Ian Shamos
Chapter 4. Convex Hulls: Extensions and Applications
Abstract
This chapter has two objectives. The first is the discussion of variants and special cases of the convex hull problem, as well as the average-case performance analysis of convex hull algorithms. The second objective is the discussion of applications that use the convex hull. New problems will be formulated and treated as they arise in these applications. Their variety should convince the reader that the hull problem is important both in practice and as a fundamental tool in computational geometry.
Franco P. Preparata, Michael Ian Shamos
Chapter 5. Proximity: Fundamental Algorithms
Abstract
In Chapter 4 we illustrated anO(NlogN)algorithm for finding the two farthest points of a plane set. One may think that finding the two closest points would be a simple extension, but it is not. The two farthest points are necessarily hull vertices and we may exploit convexity to give a fast algorithm; the two closest points do not necessarily bear any relation to the convex hull, so a new technique must be developed, which is the subject of this chapter. We will be concerned with a large class of problems that involve the proximity of points in the plane and our goal will be to deal with all of these seemingly unrelated tasks via a single algorithm, one that discovers, processes, and stores compactly all of the relevant proximity information. To do this, we revive a classical mathematical object, the Voronoi diagram, and turn it into an efficient computational structure that permits vast improvement over the best previously known algorithms. In this chapter, several of the geometric tools we have discussed earlier—such as hull-finding and searching—will be used to attack this large and difficult class—theclosest-pointorproximity problems.
Franco P. Preparata, Michael Ian Shamos
Chapter 6. Proximity: Variants and Generalizations
Abstract
The main conclusion derived from the preceding chapter is that the Voronoi diagram is both an extremely versatile tool for the solution of some fundamental proximity problems and an exceptionally attractive mathematical object in its own right. Indeed, these two facets—the instrumental and the aesthetic—have been the inspiration of a considerable amount of research on the topic. This chapter is devoted to the illustration of these extensions. Specifically, we shall at first discuss two very important applications: the already mentioned Euclidean Minimum Spanning Tree problem (and its ramifications) and the general problem of plane triangulations. We shall then show how the locus concept can be generalized in a number of directions. We shall then close the chapter with the analysis of “gaps and covers,” which will afford us a chance to appreciate the power of different computation models.
Franco P. Preparata, Michael Ian Shamos
Chapter 7. Intersections
Abstract
Much of the motivation for studying intersection problems stems from the simple fact that two objects cannot occupy the same place at the same time. An architectural design program must take care not to place doors where they cannot be opened or have corridors that pass through elevator shafts. In computer graphics, an object to be displayed obscures another if their projections on the viewing plane intersect. A pattern can be cut from a single piece of stock only if it can be laid out so that no two pieces overlap. The importance of developing efficient algorithms for detecting intersection is becoming apparent as industrial applications grow increasingly more ambitious: a complicated graphic image may involve one hundred thousand vectors, an architectural database often contains upwards of a million elements, and a single integrated circuit may contain millions of components. In such cases even quadratic-time algorithms are unacceptable.
Franco P. Preparata, Michael Ian Shamos
Chapter 8. The Geometry of Rectangles
Abstract
The methods developed earlier to intersect planar convex polygons are certainly applicable to a collection of rectangles. Similarly, a collection of segments, each of which is either parallel or orthogonal to any other member of the collection, can be handled by the general segment intersection technique described in the preceding chapter. However, the very special nature of segments having just two orthogonal directions, or of rectangles whose sides are such segments, suggests that perhaps more efficientad hoctechniques can be developed to treat such highly structured cases. And in the process of studying this class of problems one may acquire more insight into the geometric properties possessed by the objects mentioned above—rectangles and orthogonal segments—and may succeed in characterizing the wider class to which the techniques are still applicable.
Franco P. Preparata, Michael Ian Shamos
Backmatter
Metadaten
Titel
Computational Geometry
verfasst von
Franco P. Preparata
Michael Ian Shamos
Copyright-Jahr
1985
Verlag
Springer New York
Electronic ISBN
978-1-4612-1098-6
Print ISBN
978-1-4612-7010-2
DOI
https://doi.org/10.1007/978-1-4612-1098-6