000 05258nam a22005655i 4500
001 978-1-4612-1098-6
003 DE-He213
005 20220801140038.0
007 cr nn 008mamaa
008 121227s1985 xxu| s |||| 0|eng d
020 _a9781461210986
_9978-1-4612-1098-6
024 7 _a10.1007/978-1-4612-1098-6
_2doi
050 4 _aQA440-699
072 7 _aPBM
_2bicssc
072 7 _aMAT012000
_2bisacsh
072 7 _aPBM
_2thema
082 0 4 _a516
_223
100 1 _aPreparata, Franco P.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_931652
245 1 0 _aComputational Geometry
_h[electronic resource] :
_bAn Introduction /
_cby Franco P. Preparata, Michael I. Shamos.
250 _a1st ed. 1985.
264 1 _aNew York, NY :
_bSpringer New York :
_bImprint: Springer,
_c1985.
300 _aXIV, 398 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aMonographs in Computer Science,
_x2512-5486
505 0 _a1 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.
520 _aFrom 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.
650 0 _aGeometry.
_921224
650 0 _aComputer graphics.
_94088
650 0 _aAlgorithms.
_93390
650 1 4 _aGeometry.
_921224
650 2 4 _aComputer Graphics.
_94088
650 2 4 _aAlgorithms.
_93390
700 1 _aShamos, Michael I.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_931653
710 2 _aSpringerLink (Online service)
_931654
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9781461270102
776 0 8 _iPrinted edition:
_z9780387961316
776 0 8 _iPrinted edition:
_z9781461210993
830 0 _aMonographs in Computer Science,
_x2512-5486
_931655
856 4 0 _uhttps://doi.org/10.1007/978-1-4612-1098-6
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-BAE
942 _cEBK
999 _c75110
_d75110