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
Le informazioni nella sezione "Riassunto" possono far riferimento a edizioni diverse di questo titolo.
1 Introduction.- 1.1 Historical Perspective.- 1.1.1 Complexity notions in classical geometry.- 1.1.2 The theory of convex sets, metric and combinatorial geometry.- 1.1.3 Prior related work.- 1.1.4 Toward computational geometry.- 1.2 Algorithmic Background.- 1.2.1 Algorithms: Their expression and performance evaluation.- 1.2.2 Some considerations on general algorithmic techniques.- 1.2.3 Data structures.- 188.8.131.52 The segment tree.- 184.108.40.206 The doubly-connected-edge-list (DCEL).- 1.3 Geometric Preliminaries.- 1.3.1 General definitions and notations.- 1.3.2 Invariants under groups of linear transformations.- 1.3.3 Geometry duality. Polarity.- 1.4 Models of Computation.- 2 Geometric Searching.- 2.1 Introduction to Geometric Searching.- 2.2 Point-Location Problems.- 2.2.1 General considerations. Simple cases.- 2.2.2 Location of a point in a planar subdivision.- 220.127.116.11 The slab method.- 18.104.22.168 The chain method.- 22.214.171.124 Optimal techniques: the planar-separator method, the triangulation refinement method, and the bridged chain method.- 126.96.36.199 The trapezoid method.- 2.3 Range-Searching Problems.- 2.3.1 General considerations.- 2.3.2 The method of the multidimensional binary tree (k-D tree).- 2.3.3 A direct access method and its variants.- 2.3.4 The range-tree method and its variants.- 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.3.1 Early development of a convex hull algorithm.- 3.3.2 Graham’s scan.- 3.3.3 Jarvis’s march.- 3.3.4 QUICKHULL techniques.- 3.3.5 Divide-and-conquer algorithms.- 3.3.6 Dynamic convex hull algorithms.- 3.3.7 A generalization: dynamic convex hull maintenance.- 3.4 Convex Hulls in More Than Two Dimensions.- 3.4.1 The gift-wrapping method.- 3.4.2 The beneath-beyond method.- 3.4.3 Convex hulls in three dimensions.- 3.5 Notes and Comments.- 3.6 Exercises.- 4 Convex Hulls: Extensions and Applications.- 4.1 Extensions and Variants.- 4.1.1 Average-case analysis.- 4.1.2 Approximation algorithms for convex hull.- 4.1.3 The problem of the maxima of a point set.- 4.1.4 Convex hull of a simple polygon.- 4.2 Applications to Statistics.- 4.2.1 Robust estimation.- 4.2.2 Isotonic regression.- 4.2.3 Clustering (diameter of a point set).- 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.5.1 A catalog of Voronoi properties.- 5.5.2 Constructing the Voronoi diagram.- 188.8.131.52 Constructing the dividing chain.- 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.1.1 Euclidean traveling salesman.- 6.2 Planar Triangulations.- 6.2.1 The greedy triangulation.- 6.2.2 Constrained triangulations.- 184.108.40.206 Triangulating a monotone polygon.- 6.3 Generalizations of the Voronoi Diagram.- 6.3.1. Higher-order Voronoi diagrams (in the plane).- 220.127.116.11 Elements of inversive geometry.- 18.104.22.168 The structure of higher-order Voronoi diagrams.- 22.214.171.124 Construction of the higher-order Voronoi diagrams.- 6.3.2 Multidimensional closest-point and farthest-point Voronoi diagrams.- 6.4 Gaps and Covers.- 6.5 Notes and Comments.- 6.6 Exercises.- 7 Intersections.- 7.1 A Sample of Applications.- 7.1.1 The hidden-line and hidden-surface problems.- 7.1.2 Pattern recognition.- 7.1.3 Wire and component layout.- 7.1.4 Linear programming and common intersection of half-spaces.- 7.2 Planar Applications.- 7.2.1 Intersection of convex polygons.- 7.2.2 Intersection of star-shaped polygons.- 7.2.3 Intersection of line segments.- 126.96.36.199 Applications.- 188.8.131.52 Segment intersection algorithms.- 7.2.4 Intersection of half-planes.- 7.2.5 Two-variable linear programming.- 7.2.6 Kernel of a plane polygon.- 7.3 Three-Dimensional Applications.- 7.3.1 Intersection of convex polyhedra.- 7.3.2 Intersection of half-spaces.- 7.4 Notes and Comments.- 7.5 Exercises.- 8 The Geometry of Rectangles.- 8.1 Some Applications of the Geometry of Rectangles.- 8.1.1 Aids for VLSI design.- 8.1.2 Concurrency controls in databases.- 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.8.1 Intersections of rectangles.- 8.8.2 The rectangle intersection problem revisited.- 8.8.3 Enclosure of rectangles.- 8.9 Notes and Comments.- 8.10 Exercises.- References.- Author Index.Sinossi:
Le informazioni nella sezione "Su questo libro" possono far riferimento a edizioni diverse di questo titolo.
Descrizione libro Paperback. Condizione libro: New. This is an International Edition Brand New Paperback Same Title Author and Edition as listed. ISBN and Cover design differs. Similar Contents as U.S Edition. Standard Delivery within 6-14 business days ACROSS THE GLOBE. We can ship to PO Box address in US. International Edition Textbooks may bear a label "Not for sale in the U.S. or Canada" or "For sale in Asia only" or similar restrictions- printed only to discourage students from obtaining an affordable copy. US Court has asserted your right to buy and use International edition. Access code/CD may not provided with these editions. We may ship the books from multiple warehouses across the globe including Asia depending upon the availability of inventory. Printed in English. Customer satisfaction guaranteed. Codice libro della libreria US9780387961316
Descrizione libro Springer. Condizione libro: New. 0387961313 This is an International Edition. Brand New, Paperback, Delivery within 6-14 business days, Similar Contents as U.S Edition, ISBN and Cover design may differ, printed in Black & White. Choose Expedited shipping for delivery within 3-8 business days. We do not ship to PO Box, APO , FPO Address. In some instances, subjects such as Management, Accounting, Finance may have different end chapter case studies and exercises. International Edition Textbooks may bear a label "Not for sale in the U.S. or Canada" and "Content may different from U.S. Edition" - printed only to discourage U.S. students from obtaining an affordable copy. The U.S. Supreme Court has asserted your right to purchase international editions, and ruled on this issue. Access code/CD is not provided with these editions , unless specified. We may ship the books from multiple warehouses across the globe, including India depending upon the availability of inventory storage. Customer satisfaction guaranteed. Codice libro della libreria NU9780387961316
Descrizione libro Condizione libro: Brand New. PAPERBACK,Book Condition New, Brand New, Softcover, International Edition. We Do not Ship APO FPO AND PO BOX. Cover Image & ISBN may be different from US edition but contents as US Edition. Printing in English language. Quick delivery by USPS/UPS/DHL/FEDEX/ARAMEX ,Customer satisfaction guaranteed. We may ship the books from Asian regions for inventory purpose. Codice libro della libreria ABESTTND6406
Descrizione libro Paperback. Condizione libro: New. Softcover Book, Condition: New. 1st Edition. [Please Read Carefully Before Buying], This Is An International Edition. Printed In Black and White. , Book Cover And ISBN No May Be Different From US Edition. Restricted Sales Disclaimer Wordings Not For Sales In USA And Canada May Be Printed On The Cover Of The Book. Standard Shipping 7-14 Business Days. Expedited Shiping 4-8 Business Days. ***WE DO NOT ENTERTAIN BULK ORDERS.*** The Books May Be Ship From Overseas For Inventory Purpose. Codice libro della libreria 434919
Descrizione libro Paperback. Condizione libro: New. New Softcover International Edition, Printed in Black and White, Different ISBN, Same Content As US edition, Book Cover may be Different, in English Language. Codice libro della libreria 3974
Descrizione libro Condizione libro: Brand New. Brand New Paperback International Edition, Perfect Condition. Printed in English. Excellent Quality, Service and customer satisfaction guaranteed!. Codice libro della libreria AIND-7940
Descrizione libro Condizione libro: Brand New. New. SoftCover International edition. Different ISBN and Cover image but contents are same as US edition. Customer Satisfaction guaranteed!!. Codice libro della libreria SHUB99233
Descrizione libro Condizione libro: New. New. International edition. Perfect condition. Ship by express service to USA, Canada, Australia, France, Italy, UK, Germany and Netherland. Customer satisfaction our priority. Codice libro della libreria ABE-FEB-99233
Descrizione libro Condizione libro: New. Brand New Paperback International Edition.We Ship to PO BOX Address also. EXPEDITED shipping option also available for faster delivery. Codice libro della libreria AUSBNEW-7940
Descrizione libro Condizione libro: Brand New. New, SoftCover International edition. Different ISBN and Cover image but contents are same as US edition. Excellent Customer Service. Codice libro della libreria ABEUSA-99233