Computational Geometry: Algorithms and ApplicationsComputational geometry emerged from the ?eld of algorithms design and analysis in the late 1970s. It has grown into a recognized discipline with its own journals, conferences, and a large community of active researchers. The success of the ?eld as a research discipline can on the one hand be explained from the beauty of the problems studied and the solutions obtained, and, on the other hand, by the many application domains—computer graphics, geographic information systems (GIS), robotics, and others—in which geometric algorithms play a fundamental role. For many geometric problems the early algorithmic solutions were either slow or dif?cult to understand and implement. In recent years a number of new algorithmic techniques have been developed that improved and simpli?ed many of the previous approaches. In this textbook we have tried to make these modern algorithmic solutions accessible to a large audience. The book has been written as a textbook for a course in computational geometry, but it can also be used for selfstudy. 
What people are saying  Write a review
User ratings
5 stars 
 
4 stars 
 
3 stars 
 
2 stars 
 
1 star 

Review: Computational Geometry: Algorithms and Applications
User Review  Devendra Owens  GoodreadsThe defacto introduction to Computational Geometry Read full review
Review: Computational Geometry: Algorithms and Applications
User Review  Devendra Owens  GoodreadsThe defacto introduction to Computational Geometry Read full review
Contents
I  2 
II  3 
III  9 
IV  11 
V  14 
VI  16 
VII  19 
VIII  20 
LX  191 
LXI  193 
LXII  196 
LXIII  199 
LXIV  205 
LXV  208 
LXVI  214 
LXVII  215 
IX  29 
X  33 
XI  39 
XII  40 
XIII  41 
XIV  45 
XV  46 
XVI  49 
XVII  55 
XVIII  59 
XIX  60 
XX  63 
XXI  64 
XXII  66 
XXIII  71 
XXIV  76 
XXV  79 
XXVI  82 
XXVII  86 
XXVIII  89 
XXIX  91 
XXX  95 
XXXI  96 
XXXII  99 
XXXIII  105 
XXXIV  109 
XXXV  110 
XXXVI  111 
XXXVII  115 
XXXVIII  117 
XXXIX  121 
XL  122 
XLI  128 
XLII  137 
XLIII  140 
XLIV  143 
XLV  144 
XLVI  147 
XLVII  148 
XLVIII  151 
XLIX  160 
L  163 
LI  167 
LII  170 
LIII  173 
LIV  175 
LV  177 
LVI  179 
LVII  185 
LVIII  186 
LIX  188 
LXVIII  219 
LXIX  220 
LXX  226 
LXXI  231 
LXXII  237 
LXXIII  239 
LXXIV  243 
LXXV  244 
LXXVI  246 
LXXVII  250 
LXXVIII  253 
LXXIX  254 
LXXX  256 
LXXXI  257 
LXXXII  259 
LXXXIII  261 
LXXXIV  263 
LXXXV  264 
LXXXVI  268 
LXXXVII  271 
LXXXVIII  278 
LXXXIX  279 
XC  283 
XCI  284 
XCII  286 
XCIII  290 
XCIV  297 
XCV  299 
XCVI  303 
XCVII  305 
XCVIII  307 
XCIX  308 
C  309 
CI  315 
CII  318 
CIII  320 
CIV  323 
CV  324 
CVI  326 
CVII  330 
CVIII  331 
CIX  332 
CX  335 
CXI  336 
CXII  343 
CXIII  346 
CXIV  352 
CXV  353 
357  
377  
Common terms and phrases
2dimensional beach line BINARY SPACE PARTITIONS bound boundary BSP tree canonical subsets Chapter computational geometry conﬁguration space construction contains convex hull convex polygon corresponding data structure deﬁned deﬁnition Delaunay triangulation denote diagonal disc disjoint doublyconnected edge list efﬁcient endpoint event point face facets farthestpoint Voronoi Figure ﬁnd ﬁnding ﬁrst Geom geometric graph halfedge halfplanes Hence input interior intersection point kdtree leaf Lemma lies line segments linear program mesh Minkowski sum motion planning number of reported O(nlogn objects obstacles optimal partition tree planar plane sweep point location point q pointer problem prove pseudodiscs pstart quadtree query algorithm query point random range queries range searching range tree recursive region robot search path search structure Section SEGMENT INTERSECTION segment tree set of points shortest path simple polygon split storage subdivision subtree sweep line Theorem total number trapezoidal map vertex Voronoi diagram ycoordinate
Popular passages
Page 374  Halperin, and MH Overmars. The complexity of the free space for a robot moving amidst fat obstacles. Comput. Geom. Theory Appl., 3:353373, 1993.
Page 357  Geom., 19:315331, 1998. [2] PK Agarwal, M. de Berg, J. Matousek, and O. Schwarzkopf. Constructing levels in arrangements and higher order Voronoi diagrams. SIAM J. Comput., 27:654667, 1998.