Computational Geometry An Introduction

Computational Geometry An Introduction / by Franco P. Preparata, Michael I. Shamos.

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 cle...

Full description

Saved in:
Bibliographic Details
Main Authors: Preparata, Franco P. (Author), Shamos, Michael I. (Author)
Corporate Author: SpringerLink (Online service)
Format: eBook
Language:English
Published: New York, NY : Springer New York : Imprint: Springer, 1985.
Edition:1st ed. 1985.
Series:Monographs in Computer Science,
Springer eBook Collection.
Subjects:
Geometry.
Computer graphics.
Algorithms.
Electronic resources (E-books)
Online Access:Click to view e-book
Holy Cross Note:Loaded electronically.
Electronic access restricted to members of the Holy Cross Community.
Table of Contents:
  • 1 Introduction
  • 1.1 Historical Perspective
  • 1.2 Algorithmic Background
  • 1.3 Geometric Preliminaries
  • 1.4 Models of Computation
  • 2 Geometric Searching
  • 2.1 Introduction to Geometric Searching
  • 2.2 Point-Location Problems
  • 2.3 Range-Searching Problems
  • 2.4 Iterated Search and Fractional Cascading
  • 2.5 Notes and Comments
  • 2.6 Exercises
  • 3 Convex Hulls: Basic Algorithms
  • 3.1 Preliminaries
  • 3.2 Problem Statement and Lower Bounds
  • 3.3 Convex Hull Algorithms in the Plane
  • 3.4 Convex Hulls in More Than Two Dimensions
  • 3.5 Notes and Comments
  • 3.6 Exercises
  • 4 Convex Hulls: Extensions and Applications
  • 4.1 Extensions and Variants
  • 4.2 Applications to Statistics
  • 4.3 Notes and Comments
  • 4.4 Exercises
  • 5 Proximity: Fundamental Algorithms
  • 5.1 A Collection of Problems
  • 5.2 A Computational Prototype: Element Uniqueness
  • 5.3 Lower Bounds
  • 5.4 The Closest Pair Problem: A Divide-and-Conquer Approach
  • 5.5 The Locus Approach to Proximity Problems: The Voronoi Diagram
  • 5.6 Proximity Problems Solved by the Voronoi Diagram
  • 5.7 Notes and Comments
  • 5.8 Exercises
  • 6 Proximity: Variants and Generalizations
  • 6.1 Euclidean Minimum Spanning Trees
  • 6.2 Planar Triangulations
  • 6.3 Generalizations of the Voronoi Diagram
  • 6.4 Gaps and Covers
  • 6.5 Notes and Comments
  • 6.6 Exercises
  • 7 Intersections
  • 7.1 A Sample of Applications
  • 7.2 Planar Applications
  • 7.3 Three-Dimensional Applications
  • 7.4 Notes and Comments
  • 7.5 Exercises
  • 8 The Geometry of Rectangles
  • 8.1 Some Applications of the Geometry of Rectangles
  • 8.2 Domain of Validity of the Results
  • 8.3 General Considerations on Static-Mode Algorithms
  • 8.4 Measure and Perimeter of a Union of Rectangles
  • 8.5 The Contour of a Union of Rectangles
  • 8.6 The Closure of a Union of Rectangles
  • 8.7 The External Contour of a Union of Rectangles
  • 8.8 Intersections of Rectangles and Related Problems
  • 8.9 Notes and Comments
  • 8.10 Exercises
  • References
  • Author Index.

Similar Items