Computational Geometry: An IntroductionFrom 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 |
Contents
1 | |
7 | |
4 | 26 |
CHAPTER 2 | 37 |
CHAPTER 5 | 93 |
CHAPTER 3 | 95 |
CHAPTER 4 | 150 |
Fundamental Algorithms | 185 |
CHAPTER 6 | 226 |
CHAPTER 7 | 266 |
CHAPTER 8 | 323 |
374 | |
390 | |
Other editions - View all
Computational Geometry: An Introduction Franco P. Preparata,Michael Shamos No preview available - 2012 |
Computational Geometry: An Introduction Franco P. Preparata,Michael Ian Shamos No preview available - 1985 |
Computational Geometry: An Introduction Franco P. Preparata,Michael Shamos No preview available - 1993 |
Common terms and phrases
abscissae applications assume begin binary search boundary CH(S chain component computational geometry consider construction contains convex hull algorithm convex polygon convex set coordinates corresponding d-dimensional data structure defined Delaunay triangulation deleted denote determined dimensions divide-and-conquer edge Euclidean extreme points facet following theorem function geometric gift-wrapping given Graham scan half-planes half-space hyperplane insertion interior intersection interval linear lower bound method minimum spanning tree node Note number of vertices O(log O(N log O(N² obtain operations optimal P₁ and P₂ partition performance planar graph plane point set pointers polyhedron polytope preprocessing problem procedure PSLG query queue range searching recursively refer to Figure region result scan Section segment tree sequence set of points simple polygon solve sorting space step storage subfacet subset subtree supporting lines sweep-line technique transformation trapezoid triangulation U-hull U₁ U₂ update v₁ vector vertex Voronoi diagram Voronoi polygon worst-case x₁