O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

65

Computational Geometry: Fundamental Structures*

Mark de Berg

Eindhoven University of Technology

Bettina Speckmann

Eindhoven University of Technology

65.1Introduction

65.2Arrangements

Substructures and ComplexityDecompositionDuality

65.3Convex Hulls

ComplexityConstructionDynamic Convex Hulls

65.4Voronoi Diagrams

ComplexityConstructionVariations

65.5Triangulations

Delaunay TriangulationPolygonsPolyhedraPseudo-Triangulations

References

65.1Introduction

Computational geometry deals with the design and analysis of algorithms and data structures for problems involving spatial data. The questions that are studied range from basic problems such as line-segment intersection (“Compute all intersection points in a given set of line segments ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required